POJ 2762 单连通图

题意：
     给你一个有向图，问你这个图是不是单连通图，单连通就是任意两点之间至少存在一条可达路径。

思路：

     先强连通所点，重新建图，此时的图不存在环，然后我们在看看是否存在一条路径可以吧所有点都覆盖了就行了，直接一遍拓扑排序，只要拓扑排序唯一就行了，拓扑排序唯一的条件是 每次最多只能有一个进队。

#include
#include
#include
#include
#include#define N_node 1005
#define N_edge 6500
#define INF 1000000000using namespace std;typedef struct
{int to ,next;
}STAR;typedef struct
{int a ,b;
}EDGE;STAR E[N_edge] ,E1[N_edge] ,E2[N_edge];
EDGE edge[N_edge];
map<int ,map<int ,int> >mk_map;
stack<int>sk;
int list[N_node] ,list1[N_node] ,list2[N_node] ,tot;
int Belong[N_node] ,cnt;
int in[N_node] ,out[N_node];
int mark[N_node];void add(int a ,int b)
{E1[++tot].to = b;E1[tot].next = list1[a];list1[a] = tot;E2[tot].to = a;E2[tot].next = list2[b];list2[b] = tot;
}void _add(int a ,int b)
{E[++tot].to = b;E[tot].next = list[a];list[a] = tot;
}void DFS_1(int s)
{mark[s] = 1;for(int k = list1[s] ;k ;k = E1[k].next){int xin = E1[k].to;if(!mark[xin])DFS_1(xin);}sk.push(s);
}void DFS_2(int s)
{mark[s] = 1;Belong[s] = cnt;for(int k = list2[s] ;k ;k = E2[k].next){int xin = E2[k].to;if(!mark[xin])DFS_2(xin);}
}bool TP_sort(int n)
{queue<int>q;int ss = 0;for(int i = 1 ;i <= n ;i ++){if(in[i] == 0){q.push(i);ss ++;if(ss > 1) return 0;}}int sot = 0;while(!q.empty()){int xin ,tou;tou = q.front();q.pop();sot ++;ss = 0;for(int k = list[tou] ;k ;k = E[k].next){xin = E[k].to;if(--in[xin] == 0){  ss ++;q.push(xin);if(ss > 1) return 0;}}}return sot == n;
}int main ()
{int t ,n ,m;int a ,b ,i;scanf("%d" ,&t);while(t--){scanf("%d %d" ,&n ,&m);memset(list1 ,0 ,sizeof(list1));memset(list2 ,0 ,sizeof(list2));tot = 1;for(i = 1 ;i <= m ;i ++){scanf("%d %d" ,&a ,&b);add(a ,b);edge[i].a = a ,edge[i].b = b;}memset(mark ,0 ,sizeof(mark));while(!sk.empty())sk.pop();for(int i = 1 ;i <= n ;i ++)if(!mark[i]) DFS_1(i);cnt = 0;memset(mark ,0 ,sizeof(mark));while(!sk.empty()){int xin = sk.top();sk.pop();if(mark[xin]) continue;cnt ++;DFS_2(xin);}mk_map.clear();memset(in ,0 ,sizeof(in));memset(out ,0 ,sizeof(out));memset(list ,0 ,sizeof(list));tot = 1;for(i = 1 ;i <= m ;i ++){a = Belong[edge[i].a];b = Belong[edge[i].b];if(a == b || mk_map[a][b]) continue;mk_map[a][b] = 1;in[b] ++ ,out[a] ++;_add(a ,b);}if(TP_sort(cnt)) puts("Yes");else puts("No");}return 0;
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！