![[强连通分量] POJ 2762 Going from u to v or from v to u?](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "[强连通分量] POJ 2762 Going from u to v or from v to u?")
Going from u to v or from v to u?
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 17089 | Accepted: 4590 |
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
原题大意：T组数据，每组数据输入点的个数n和边的个数m，接下来m行输入a,b，表示从a到b有一条有向边，问是否每两个点之间存在通路（即a->b和b->a任意存在一条即可）。
解题思路：首先这是一个连通问题，我们要看是否连通，为了让算法变得简单，可以将原图中所有强连通分量看作一个点，于是要先缩点。
于是，先将整个图用tarjian标记，然后缩点成DAG图（有向无环图，简称G图）。
接下来我们考虑这个G图，想一下首先，如果其中一个点（即原图中一个强连通分量）的出度>1，那么很显然，它所指向的另外几个点互不相通。
那么解法就来了：
假设G图中入度为0的点为起点，它所指向的点为子节点，那么每个点只能有一个子节点。
也就是说，这个G图中各个点链接像单向链表的时候满足题意。
于是我们可以简单模拟（也就是用入度和出度和它们的方向暴力一遍），也可以改一下拓扑排序，判断是否为单链。
最后输出答案就可以了。
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
queue<int> q;
struct list
{
int v;
list *next;
};
list *head[],*rear[],*map_head[],*map_rear[];
int stack[],s[],dfn[],low[],indegree[];
bool instack[];
int top,cnt,times;
void tarjian(int v)
{
dfn[v]=low[v]=++times;
stack[top++]=v;
instack[v]=true;
for(list *p=head[v];p!=NULL;p=p->next)
if(!dfn[p->v])
{
tarjian(p->v);
if(low[p->v]<low[v]) low[v]=low[p->v];
} else if(low[p->v]<low[v]&&instack[p->v]) low[v]=low[p->v];
if(dfn[v]==low[v])
{
++cnt;
do
{
v=stack[--top];
instack[v]=false;
s[v]=cnt;
}while(dfn[v]!=low[v]);
}
return;
}
bool topsort()
{
int count=,i;
while(!q.empty()) q.pop();
for(i=;i<=cnt;++i)
{
if(!indegree[i])
{
++count;
q.push(i);
}
}
if(count>) return false;
while(!q.empty())
{
int u=q.front();
q.pop();
count=;
for(list *p=map_head[u];p!=NULL;p=p->next)
{
--indegree[p->v];
if(!indegree[p->v])
{
++count;
q.push(p->v);
}
}
if(count>) return false;
}
return true;
}
int main()
{
int T,n,m,i,u,v,a,b,num;
scanf("%d",&T);
while(T--)
{
memset(head,,sizeof(head));
memset(rear,,sizeof(rear));
scanf("%d%d",&n,&m);
for(i=;i<m;++i)
{
scanf("%d%d",&u,&v);
if(rear[u]!=NULL)
{
rear[u]->next=new list;
rear[u]=rear[u]->next;
}else head[u]=rear[u]=new list;
rear[u]->v=v;
rear[u]->next=NULL;
}
top=times=cnt=;
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(stack,,sizeof(stack));
memset(instack,false,sizeof(instack));
memset(s,,sizeof(s));
for(i=;i<=n;++i) if(!dfn[i]) tarjian(i);
memset(map_head,,sizeof(map_head));
memset(map_rear,,sizeof(map_rear));
memset(indegree,,sizeof(indegree));
for(i=;i<=n;++i)
for(list *p=head[i];p!=NULL;p=p->next)
if(s[i]!=s[p->v])
{
++indegree[s[p->v]];
if(map_rear[s[i]]!=NULL)
{
map_rear[s[i]]->next=new list;
map_rear[s[i]]=map_rear[s[i]]->next;
} else map_head[s[i]]=map_rear[s[i]]=new list;
map_rear[s[i]]->v=s[p->v];
map_rear[s[i]]->next=NULL;
}
if(topsort()) printf("Yes\n");
else printf("No\n");
}
return ;
}