POJ 2762 Going from u to v or from v to u? (强连通分量缩点+拓扑排序)

题意是有t组样例，n个点m条有向边，取任意两个点u和v，问u能不能到v 或者v能不能到u，要是可以就输出Yes，否则输出No。注意一点，条件是或者！所以不是判断双连通图的问题。

我一开始没看到'or'这个条件，所以直接tarjan判断是否只有一个强连通分量，果断WA。

所以需要给原图缩点，用tarjan把图变成一个有向无环图，要是只有一个scc，那就直接输出Yes。那接下来讨论多个scc，要是新图中有两个及以上的点的入度为0，则这些点都不能相互到达，所以输出No，所以我们找到唯一一个入度为0的点作为root，然后从这个点来拓扑排序，出队入队的过程肯定是一进一出的，所以根据过程来判断是否输出Yes和No。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <vector>

 #include <queue>

 using namespace std;

 const int MAXN = ;

 struct data {

     int next , to;

 }edge[MAXN * ];

 int head[MAXN] , st[MAXN] , low[MAXN] , dfn[MAXN] , block[MAXN] , du[MAXN];

 int top , ord , sccnum , cont;

 bool instack[MAXN];

 vector <int> G[MAXN];

 inline void add(int u , int v) {

     edge[cont].next = head[u];

     edge[cont].to = v;

     head[u] = cont++;

 }

 void init() {

     memset(head , - , sizeof(head));

     memset(dfn ,  , sizeof(dfn));

     memset(du ,  , sizeof(du));

     memset(instack , false , sizeof(instack));

     top = sccnum = ord = cont = ;

 }

 void tarjan(int u) {

     low[u] = dfn[u] = ++ord;

     st[++top] = u;

     instack[u] = true;

     for(int i = head[u] ; ~i ; i = edge[i].next) {

         int v = edge[i].to;

         if(!dfn[v]) {

             tarjan(v);

             low[u] = min(low[u] , low[v]);

         }

         else if(instack[v]) {

             low[u] = min(low[u] , low[v]);

         }

     }

     if(low[u] == dfn[u]) {

         int v;

         sccnum++;

         do {

             v = st[top--];

             instack[v] = false;

             block[v] = sccnum;

         }while(u != v);

     }

 }

 void top_sort() {

     queue <int> que;

     while(!que.empty()) {

         que.pop();

     }

     cont = ;

     for(int i =  ; i <= sccnum ; i++) {

         if(!du[i]) {

             que.push(i);

             cont++;

         }

     }

     if(cont > ) {

         printf("No\n");

         return ;

     }

     while(!que.empty()) {

         int temp = que.front() , cnt = ;

         que.pop();

         for(int i =  ; i < G[temp].size() ; i++) {

             du[G[temp][i]]--;

             if(!du[G[temp][i]]) {

                 cnt++;

                 cont++;

                 que.push(G[temp][i]);

             }

         }

         if(cnt > ) {

             printf("No\n");

             return ;

         }

     }

     if(cont != sccnum) {

         printf("No\n");

     }

     else {

         printf("Yes\n");

     }

 }

 int main()

 {

     int t , n , m , u , v;

     scanf("%d" , &t);

     while(t--) {

         scanf("%d %d" , &n , &m);

         init();

         for(int i =  ; i < m ; i++) {

             scanf("%d %d" , &u , &v);

             add(u , v);

         }

         for(int i =  ; i <= n ; i++) {

             G[i].clear();

             if(!dfn[i])

                 tarjan(i);

         }

         if(sccnum == ) {

             printf("Yes\n");

             continue;

         }

         for(int u =  ; u <= n ; u++) {

             for(int i = head[u] ; ~i ; i = edge[i].next) {

                 int v = edge[i].to;

                 if(block[u] != block[v]) {

                     du[block[v]]++;

                     G[block[u]].push_back(block[v]);

                 }

             }

         }

         top_sort();

     }

 }

巴特西

POJ 2762 Going from u to v or from v to u? (强连通分量缩点+拓扑排序)

最新文章

热门文章