自学教程：C++ DFS函数代码示例

bool TopologicalGraph::CheckBiconnected()  {if(debug())DebugPrintf("   CheckBionnected");  if(Set().exist(PROP_BICONNECTED))return true;  if(nv() < 3 || ne() < 3)return false;  if(debug())DebugPrintf("Executing CheckBionnected");  int m = ne();  int n = nv();  if (m==0) return true;  svector<tvertex> nvin(-m,m);   nvin.SetName("TG:Bicon:nvin");  svector<tvertex> low(0,n);     low.SetName("TG:Bicon:low");   if(!DFS(nvin)) // not connected ...      return false;  _Bicon Bicon(n);  int ret = bicon(n,m,nvin,Bicon,low);  if(ret)      {Prop1<int> isbicon(Set(),PROP_BICONNECTED);      Prop1<int> is_con(Set(),PROP_CONNECTED);      return true;      }  return false;  }

void ListComponents(){    int i;    for (i = 0; i < G->n; i++) {        if (!G->Visited[i]) {            printf("{ ");            DFS(i);            printf("}/n");        }    }    for (i = 0; i < G->n; i++)        G->Visited[i] = 0;    for (i = 0; i < G->n; i++) {        if (!G->Visited[i]) {            printf("{ ");            BFS(i);            printf("}/n");        }    }}

int DFS(int x){    visx[x] = 1;    for (int y = 1;y <= ny;y ++)    {        if (visy[y])            continue;        int t = lx[x] + ly[y] - w[x][y];        if (t == 0)       //        {            visy[y] = 1;            if (link[y] == -1||DFS(link[y]))            {                link[y] = x;                return 1;            }        }        else if (slack[y] > t)  //不在相等子图中slack 取最小的            slack[y] = t;    }    return 0;}

//************factorization part function***************void DFS(int u){	int v,i,h,temp,j=0;	int rootlist[n];	//initialize rootlist	for(i=0;i<n;i++)		rootlist[i]=0;	if( cal_Qy_zero(u) )			output_message_poly(u);     	else if( deg[u] < (k-1) )		// the "D" of thesis represent k-1	{		//try n field element to calculate the y-root of Q(0,y)=0		for(h=(n-1);h>=0;h--)		//field element from large to small		{			temp=cal_rootlist(u,h);			if( temp == 0 )			{					rootlist[j]=a[h];				j++;			}		}		for(i=0;i<n;i++)			if( rootlist[i]!=0 )			{				v=time;				time=time+1;				last[v]=u;				deg[v]=deg[u]+1;				Coeff[v]=rootlist[i];				cal_update_poly(v,u,rootlist[i]);  				DFS(v);			}	}	}

int maxMatch() {	for (int i = 0; i < N; ++i) used[i] = false;	for (int i = 0; i < N; ++i) matchX[i] = -1;	for (int i = 0; i < M; ++i) matchY[i] = -1;	for (int i = 0; i < N; ++i) level[i] = -1;	int match = 0, d;	for ( ; ; match += d) {		static int Q[MAXN * 2 + 1];		int head = 0, tail = d = 0;		for (int x = 0; x < N; ++x) level[x] = -1;		for (int x = 0; x < N; ++x) if (matchX[x] == -1)			level[x] = 0, Q[++tail] = x;		while (head < tail)			for (edge e(fir[x = Q[++head]]); e; e = e->next) {				int y = e->to, z = matchY[y];				if (z != -1 && level[z] < 0) level[z] = level[x] + 1, Q[++tail] = z;			}		for (int x = 0; x < N; ++x) used[x] = false;		for (int x = 0; x < N; ++x) if (matchX[x] == -1) if (DFS(x)) ++d;		if (d == 0) break;	} return match;}

bool solve(int mid){    top=0;    memset(vert,0,sizeof(vert));    memset(r_vert,0,sizeof(r_vert));    for(int i=0;i<mid;i++)    {        Add_Edge(door[i][0],oppo[door[i][1]]);        Add_Edge(door[i][1],oppo[door[i][0]]);    }    memset(v,0,sizeof(v));top=0;    memset(order,0,sizeof(order));    for(int i=0;i<2*n;i++)        if(!v[i])DFS(i);    memset(v,0,sizeof(v));top=1;    memset(id,0,sizeof(id));    for(int i=2*n-1;i>=0;i--)        if(!v[order[i]]){RG_DFS(order[i]);top++;}    for(int i=0;i<2*n;i++)        if(id[i]==id[oppo[i]])return false;    return true;}

main() {    freopen("in.txt", "rt", stdin);      freopen("out2.txt", "w+t", stdout);    clock_t st, ed;    st = clock();    int a, x;	while(scanf("%d", &n) == 1) {		for(a = 0; a < n; a++)			next[a] = a+1;		memset(Last, 0, sizeof(Last));		memset(map, 0, sizeof(map));		for(a = 1; a <= n; a++) {			while(scanf("%d", &x) == 1 && x != 0)				map[a][x-1] = 1;		}		next[n] = 0;		DFS(n, 0);	}    ed = clock();    /*printf("%f/n", (float)(ed - st )/CLOCKS_PER_SEC);*/	return 0;}

void DFS(int k) {	if(k > len) return;	if(DL[head].right == head) {		if(k < len) len = k;		return;	}	int t = Maxv, c, i, j;	for(i = DL[head].right; i != head; i = DL[i].right) {		if(s[i] < t) {			t = s[i], c = i;		}	}	remove(c);	for(i = DL[c].down; i != c; i = DL[i].down) {		for(j = DL[i].right; j != i; j = DL[j].right)			remove(DL[j].ch);		DFS(k+1);		for(j = DL[i].left; j != i; j = DL[j].left)			resume(DL[j].ch);	}	resume(c);}

Tarjan::Tarjan(Graph *graph){	m_pre = 0;	m_numSCC = 0;	m_graph = graph;	m_numNodes = graph->getNNodes();	m_visited = new bool[graph->getNNodes()];	m_sccGroupID = new int[graph->getNNodes()];	m_low = new int[graph->getNNodes()];	for (int i = 0; i < graph->getNNodes(); i++) 	{	m_visited[i] = false;		m_sccGroupID[i] = 0;		m_low[i] = 0;	}	for (int i = 0; i < graph->getNNodes(); i++) 	{	if (!m_visited[i]) DFS(graph, i);	}}

int main(){    while(scanf("%d",&n)!=EOF)    {        top=-1;        for(int i=1;i<=n;i++)vert[i]=r_vert[i]=NULL;        for(int i=1;i<=n;i++)        {            int j;            while(scanf("%d",&j),j) Add_Edge(i,j);        }        top=1;        memset(visit,0,sizeof(visit));        for(int i=1;i<=n;i++)            if(!visit[i])DFS(i);                top=0;        memset(visit,0,sizeof(visit));        for(int i=n;i>0;i--)            if(!visit[order[i]]){DFS_RG(order[i]);top++;}                memset(in,0,sizeof(in));        memset(out,0,sizeof(out));        for(int i=1;i<=n;i++)            for(edge *p=vert[i];p;p=p->next)                if(id[i]!=id[p->to])                    out[id[i]]++,in[id[p->to]]++;        int m1=0,m2=0,m3=0;        for(int i=0;i<top;i++)        {            if(in[i]==0&&out[i]==0)m3++;            else if(!in[i])m1++;            else if(!out[i])m2++;        }        printf("%d/n%d/n",m1+m3,m3+(m1>m2?m1:m2));    }    return 0;}

int main() {	//freopen("in.txt", "r", stdin);	int nca;	scanf("%d", &nca);	while (nca--) {		int top = -1;		memset(vert, 0, sizeof (vert));		scanf("%d%d", &n, &m);		for (int x, y, i = 0; i < m; i++) {			scanf("%d%d", &x, &y);			add_edge(x, y, top);			add_edge(y, x, top);		}		memset(dep, 0, sizeof (dep));		memset(anc, 0, sizeof (anc));		memset(par, -1, sizeof (par));		memset(color, 0, sizeof (color));		for (int i = 1; i <= n; i++) {			if (!color[i])DFS(i, -1, 1);		}		memset(anc, 0, sizeof (anc));		for (int ii, i = 1; i <= n; i++) {			ii = my_find(i);			anc[ii]++;		}		int ans = 0;		for (int ii, i = 1; i <= n; i++) {			ii = my_find(i);			int tem = anc[ii];			if (ans < tem) {				ans = tem;			}		}		if (ans == 1)ans = 0;		printf("%d/n", ans);	}	return 0;}

int main() {    FILE* fp = fopen("DFS.txt", "r");     int vertex_num;     ADJACENT_LIST graph;      fscanf(fp, "%d/n", &vertex_num);     int tmp;     int i;     for(i = 1; i <= vertex_num; ++i) {        fscanf(fp, "%d", &tmp);         graph[i] = (NODE)malloc(sizeof(struct node));         NODE node_p = graph[i];         node_p->data = tmp;         node_p->next = NULL;         while(tmp != -1) {                       fscanf(fp, "%d", &tmp);             node_p->next = (NODE)malloc(sizeof(struct node));             node_p = node_p->next;             node_p->data = tmp;             node_p->next = NULL;         }    }    fclose(fp);     freopen("DFS.out", "w", stdout);     result = NULL;     DFS(graph, vertex_num);     return 0; }

int main(void){    int n;    printf("How many vertices you want to take?");    scanf("%d",&n);    initialize(n);    insertEdges(n);    DFS(n);    sortVertices(n);    checker = 1;    initialize(n);    reverseDirection(n);    for(int i = 1; i <= n; i++)    {        int v = s_vertices[i];        if(color[v] == 0)        {            c = 0;            DFS_Visit(n, v);            for(int j = 1; j <= c; j++)            {                if(j == 1)                {                    printf("%d ", ver[j]);                }                else{                    printf(", %d",ver[j]);                }            }            printf("/n");        }    }return 0;}

intmain(int argc, char **argv){        int i = 0, j = 0;        int blank = 0;        while (1) {                /* read input                 */                scanf("%d%d", &N, &L);                for (i = 0; i < N; i++)                        for (j = 0; j < N; j++)                                scanf("%d", &G[i][j]);                /* initialize                 */                len = 0, flag = 0;                memset(visit, 0, sizeof(visit));                path[0] = 1;                visit[0] = 1;                /* generate output                 */                if (blank)                        putchar('/n');                blank = 1;                DFS(0);                if (flag == 0)                        printf("no walk of length %d/n", L);                /* get rid of -9999                 */                if (scanf("%d", &i) == EOF)                        break;        }        return 0;}

void save(pos p[]){	int j;	pos zero;	zero.x=0;	zero.y=0;	if(step+DIS>=50){			answer=1;	} else {		for(j=0;j<num;j++){							//	printf("The distance is :%lf /n",distance(zero,p[j]));			if(visited[j]==0 && distance(zero,p[j]) <= DIS+step){				answer=DFS(p,j);			if(answer==1)				break;						}							}	}	if(answer==1)		printf("Yes");	else		printf("No");}

void solve(void){ unsigned i, maxi;  /* инициализация */  for (i = 0; i < n; i++) {    maxDist[i] = 0;    savePath[i] = -1;  }  for (i = 0; i < n; i++)    if (maxDist[i] == 0) DFS(i);  maxi = 0;  for (i = 0; i < n; i++)    if (maxDist[i] > maxDist[maxi]) maxi = i;  printf("Дължината на критичния път е %d/nПътят е: ", maxDist[maxi]);  while (savePath[maxi] >= 0) {    printf("%d ", maxi + 1);    maxi = savePath[maxi];  }  printf("%u/n", maxi + 1);}

void DFS(vector<int>& nums, int gap, vector<int>& intermediate, vector<vector<int>>& result){    if(gap == 0)    {        result.push_back(intermediate);    }    for(int i = 0; i < nums.size(); i++)    {        if( gap - nums[i] >= 0)//剪枝        {            if(intermediate.empty() || nums[i] >= intermediate.back())//剪枝            {                intermediate.push_back(nums[i]);                DFS(nums, gap-nums[i], intermediate, result);                intermediate.pop_back();            }        }        else        {            break;        }    }}

main() {	while(scanf("%d %d", &N, &M) == 2) {		getchar();		for(i = 0; i < N; i++) {			scanf("%s", map[i]);		}		while(M--) {			scanf("%s", s);			flag = 0;			for(i = 0; i < N; i++)				for(j = 0; j < N; j++) {					if(map[i][j] == s[0] && flag == 0) {						DFS(i, j, 0);					}				}			if(!flag)				printf("No/n");			else				printf("Yes/n");		}	}	return 0;}

 void DFS(int depth) {     if(depth == row)     {         result.push_back(tmpResult);         return;     }     for(int i = 0; i < col; ++i)     {         if(!colMark[i] && !leftUp[depth-i+row] && !rightUp[depth+i])         {             colMark[i] = true;             leftUp[depth-i+row] = true;             rightUp[depth+i] = true;             tmpResult[depth][i] = 'Q';             DFS(depth+1);             colMark[i] = false;             leftUp[depth-i+row] = false;             rightUp[depth+i] = false;             tmpResult[depth][i] = '.';         }     } }

int DFS(int T, int now, int start, int *p) {    int last = oo, i, j, tmp, flag = 0, ttry = 0;    Time[now] = T;    int findmain = 0;    for(i = 0, j = NodeL[now]; i < NodeT[now]; i++, j++) {        if(Used[data[j].y] == 0) {            Used[data[j].y] = 1;            tmp = DFS(T+1, data[j].y, 0, &findmain);            if(tmp >= T)    flag = 1;            last = tmp < last ? tmp : last;            ttry++;        } else {            tmp = Time[data[j].y];            last = tmp < last ? tmp : last;        }    }    if(start != 1 && findmain == 1) {		if(flag)			Ans[now] = 1;    }    if(now == 0 || findmain == 1)	*p = 1;    return last;}

 void DFS(int x, int y, string &s, TrieNode *r, vector<vector<char> > &b) {     if (r == NULL) {         return;     }     if (r->isWord) {         // A word is found         us.insert(s);     }     int x1, y1;     int i;     for (i = 0; i < 4; ++i) {         x1 = x + d[i][0];         y1 = y + d[i][1];         if (!inbound(x1, y1) || v[x1][y1]) {             continue;         }         v[x1][y1] = true;         s.push_back(b[x1][y1]);         DFS(x1, y1, s, r->child[b[x1][y1] - 'a'], b);         s.pop_back();         v[x1][y1] = false;     } }

void DFS(int u,int f){    dfn[u]=low[u]=++index;    Stack[top++]=u, InStack[u]=1;    for(int i=0;i<(int)G[u].size();i++){        int v=G[u][i];        if(!dfn[v]){            DFS(v,u);            low[u]=min(low[u],low[v]);        }else if(InStack[v])            low[u]=min(low[u],dfn[v]);    }    int j;    if(dfn[u]==low[u]){        scc++;        while((j=Stack[--top])){//node >=1            InStack[j]=0;            Belong[j]=scc;            SCC[scc].push_back(j);            if(j==u) break;        }    }}

void DFS(int node, pt_net nt){  int k;  if(connected)    return;  if(node == nt->t){    connected=1;    return;  }  visited[node]=1;  k=1;  while(list[node][k]>0){    if(!visited[list[node][k]])      DFS(list[node][k],nt);    k++;  }    return;}

void DFS( int* G, const int& N  ) {        if( top + N <= maxi )   return;        if( top > maxi )        maxi = top;    for( int i = 0; i < N; ++i ) {                Clique[top++] = G[i];        int P[50],  M = 0;        for( int j = i + 1; j < N; ++j )            if( B[G[i]][G[j]] )                P[M++] = G[j];        DFS( P, M );        --top;            }}

 void DFS(int u, int f) {   dfn[u] = low[u] = step++;   stk[top++] = u;   for (auto v:E[u]) {     if (v == f) continue;     if (dfn[v] == -1) {       DFS(v,u);       low[u] = min(low[u], low[v]);       if (low[v] >= dfn[u]) {         int z;         sccv[nScc].clear();         do {           z = stk[--top];           sccv[nScc].PB(z);         } while (z != v);         sccv[nScc].PB(u);         nScc++;       }     } else {       low[u] = min(low[u],dfn[v]);     }   } }

int main(){    scanf("%d", &T);    while(T--){        scanf("%d", &n);        memset(V, 0, sizeof(V));        judge = 0;        int sum = 0, Max = 0;        for(int i = 0; i < n; i++){            scanf("%d", &num[i]);            sum += num[i];            if(num[i] > Max)    Max = num[i];        }        avg = sum/4;        std::sort(num, num+n, cmp);        if(sum%4 || Max > avg)    puts("no");        else{            DFS(0, 0, 0, 0);            puts(judge?"yes":"no");        }    }    return 0;}

 vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries)  {     for (int i=0; i<equations.size(); i++)     {         next[equations[i].first].push_back(equations[i].second);         value[equations[i].first+":"+equations[i].second]=values[i];         next[equations[i].second].push_back(equations[i].first);         value[equations[i].second+":"+equations[i].first]=1.0/values[i];         visited[equations[i].first]=0;         visited[equations[i].second]=0;     }          vector<double>results;          for (int i=0; i<queries.size(); i++)     {         for (auto a:visited)             visited[a.first]=0;                     results.push_back(DFS(queries[i].second,queries[i].first));     }                  return results; }

main() {	int n, a, b, A[501];	while(scanf("%d", &n) == 1) {		memset(Mt, 0, sizeof(Mt));		for(a = 1; a <= n; a++)			scanf("%d", &A[a]);		for(a = 1; a <= n; a++)			for(b = a+1; b <= n; b++)				if(A[b] > A[a])					map[a][Mt[a]++] = b;		memset(mx, 0, sizeof(mx));		memset(my, 0, sizeof(my));		int Ans = 0;		for(a = 1; a <= n; a++)			if(!mx[a]) {				memset(used, 0, sizeof(used));				if(DFS(a))					Ans++;			}		printf("%d/n", n-Ans);	}	return 0;}

void GraphAdjArray::DFSTraverse(GraphEnumProc pProc, void* lParam){	if(vexnum <= 0)	{		return;	}	bool* visited = new bool[vexnum];	memset(visited, 0, sizeof(bool) * vexnum);	for(int i = 0; i < vexnum; i++)	{		if(visited[i])		{			continue;		}		if(!DFS(pProc, lParam, i, visited))		{			return;		}	}	delete [] visited;}

int AI::IDDFS(int maxDepth){  int retVal,depth = 0;    Move move(-1, 0, HEAD, -1, -1);    while(depth < maxDepth)  {     if (outFlag == true)    {      cout<<"/n/n/n------------------------------------running DFS w/ depth:";      cout<<depth<<endl;    }    retVal = DFS(depth);    tree.clear();    tree.insert(move);    depth++;    if(retVal >= 0)    {      break;    }  }  return retVal;}