首页 > 代码库 > POJ 2762判断单联通(强连通缩点+拓扑排序）
POJ 2762判断单联通(强连通缩点+拓扑排序）
Going from u to v or from v to u?
Description In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridors connecting some rooms. Each time, Wind choose two rooms x and y, and ask one of their little sons go from one to the other. The son can either go from x to y, or from y to x. Wind promised that her tasks are all possible, but she actually doesn‘t know how to decide if a task is possible. To make her life easier, Jiajia decided to choose a cave in which every pair of rooms is a possible task. Given a cave, can you tell Jiajia whether Wind can randomly choose two rooms without worrying about anything? Input The first line contains a single integer T, the number of test cases. And followed T cases. The first line for each case contains two integers n, m(0 < n < 1001,m < 6000), the number of rooms and corridors in the cave. The next m lines each contains two integers u and v, indicating that there is a corridor connecting room u and room v directly. Output The output should contain T lines. Write ‘Yes‘ if the cave has the property stated above, or ‘No‘ otherwise. Sample Input 1 3 3 1 2 2 3 3 1 Sample Output Yes Source POJ Monthly--2006.02.26,zgl & twb |
[Submit] [Go Back] [Status] [Discuss]
题意：对于任意两个节点u，v，如果能从u到v或者v到u，那么输出Yes，否则输出No。
思路：先强连通缩点，此时一定不含环，看能不能找到一条最长路包含所有的缩点就行（实际上是找判断单链），用拓扑排序就ok,不过如果只有一个强连通分量那么一定是Yes啦，否则topo排序判断 ，代码如下：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn =1e4+10;
const ll mod=20140413;
vector<int>G1[maxn],G2[maxn],G[maxn];
int sccno[maxn],vis[maxn],scc_cnt;//sccno强连通编号，scc_cnt表示强连通分量的个数
int ind[maxn];//ind表示入度
void init_G(int n)//初始化缩点图
{
memset(ind,0,sizeof ind);
for(int i=1;i<=n;i++)G[sccno[i]].clear();
for(int i=1;i<=n;i++) {
for(int j=0;j<G1[i].size();++j){
int &v =G1[i][j];
if(sccno[i]!=sccno[v]) {
G[sccno[i]].push_back(sccno[v]);
ind[sccno[v]]++;
}
}
}
}
bool toposort(int n)//topo排序
{
init_G(n);
int u,cnt=0;
queue<int>q;
for(int i=1;i<=n;i++){
if(!ind[sccno[i]]){
if(!q.empty())return false;
q.push(sccno[i]);
cnt++;
}
}
while(!q.empty()){
u=q.front();
q.pop();
ind[u]=-1;
for(int i=0;i<G[u].size();i++) {
int &v=G[u][i];
ind[v]--;
if(ind[v]==0){
if(!q.empty())return false;
q.push(v);
cnt++;
}
}
}
return cnt==scc_cnt;
}
vector<int>S;
void init(int n)
{
memset(vis,0,sizeof vis);
memset(sccno,0,sizeof sccno);
S.clear();
scc_cnt=0;
for(int i=1;i<=n;i++) {
G1[i].clear();
G2[i].clear();
G[i].clear();
}
}
void AddEdge(int u,int v)
{
G1[u].push_back(v);
G2[v].push_back(u);
}
void dfs1(int u)
{
if(vis[u])return ;
vis[u]=1;
for(int i=0;i<G1[u].size();i++)dfs1(G1[u][i]);
S.push_back(u);
}
void dfs2(int u)
{
if(sccno[u]) return ;
sccno[u]=scc_cnt;
for(int i=0;i<G2[u].size();++i)dfs2(G2[u][i]);
}
bool is_Semiconnect(int n)///计算强连通分量，初步判断
{
for(int i=1;i<=n;i++)dfs1(i);
for(int i=S.size();i>=1;i--){
if(!sccno[S[i-1]]){
scc_cnt++;
dfs2(S[i-1]);
}
}
return scc_cnt<=1;
}
int main()
{
int T,n,m;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);
int u,v;
init(n);
while(m--) {
scanf("%d%d",&u,&v);
AddEdge(u,v);
}
if(is_Semiconnect(n))puts("Yes");
else{
if(toposort(n))puts("Yes");
else puts("No");
}
}
return 0;
}POJ 2762判断单联通(强连通缩点+拓扑排序）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。