## poj 2672 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: 8032 Accepted: 1892

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`
`题目：给定一个图，问你是否对于任意的定点对x,y，能找到一条从x到y 或从y到x的路径，（满足一条即可）；`
`类型：弱连通分量。`
`解法：`
`这题花了很长时间，至少花了两个小时，到后来都想吐了，这让我更恶心到了两遍dfs求强连通分量的复杂。还好做出来了，虽然800+ms，还是挺爽的。`
`n： 1000，  m： 6000`
`原来什么都没想就开始做，每次spfa(x,y)，尝试从x找到一条道y的路径，果断TLE。其实肯定TLE，不知道当时怎么想的。`
`这题先求强连通分量，缩点，形成一棵新的树，这样主要是为了利用一些性质。若图是弱连通的，缩点后的树必须满足一下性质：`
`1，形成的是一棵树：这是必须的。否则从一棵树的点到另一棵树无法到达。`
`2，这棵树有且仅有一个点的入度是0, 如果有多个的话那么这些入度为0的点是不可以互相到达的。`
`3, 从这个入度为0的点进行dfs，找到的是一条链，就是不会有分叉，如果有的话，则两个分叉的点互相不可达。`
`（这点其实我不明白，应该是找条最长链的）`
`代码超级乱：`
```
Source Code

Problem: 2762

User: hehexiaobai

Memory: 9084K

Time: 891MS

Language: C++

Result: Accepted

Source Code
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXV = 1005;
const int MAXE = 6005;
int f[MAXV];
int sblg[MAXV];
int m, n, cntf,nstrong;
bool visit[MAXV];
bool strong[MAXV][MAXV];
int in[MAXV];
void dfs1(int u)
{
visit[u] = true;
for(int i = 1; i <= adj[u][0]; i ++)
f[cntf] = u;
cntf --;
}
void dfs2(int u, int nstrong)
{
visit[u] = true;
sblg[u] = nstrong;
for(int i = 1; i <= adj_op[u][0]; i ++)
}
bool flag ;
void dfs(int u)
{
visit[u] = true;
int c = 0;
for(int i = 1; i <= nstrong; i ++)
{
if(strong[u][i])
{
dfs(i);
c ++;
}
}
if(c > 1)flag = false;
}
int main()
{
int t,i,j, u, v;
scanf("%d",&t);
while(t--)
{
memset(f,0,sizeof f);
scanf("%d %d",&n, &m);
for(i = 0; i < m; i ++)
{
scanf("%d %d",&u, &v);
}
memset(visit, 0, sizeof visit);
cntf = n ;
for(i = 1; i <= n; i ++)
if(!visit[i]) dfs1(i);
memset(visit, 0, sizeof visit);
memset(sblg, 0, sizeof (sblg));
nstrong = 0;
for(i = 1; i <= n;i ++)
if(!visit[f[i]])
{
nstrong ++ ;
dfs2(f[i], nstrong);
}
if(nstrong == 1)
{
printf("Yes\n");
continue;
}
memset(in, 0, sizeof in);
memset(strong, 0,sizeof strong);
for( i  = 1; i <= n; i ++)
for(j = 1; j <= adj[i][0]; j++ )
{
}
int index = -1;
for(i = 1;i <= n; i ++)
if(in[sblg[i]] == false)
{
index = sblg[i];
break;
}
flag = true;
memset(visit, 0, sizeof visit);
dfs(index);
/*	for(i = 1; i <= nstrong; i ++,cout << endl)
for(j = 1; j <= nstrong; j ++)
cout << strong[i][j]<<' ';
*/
for(i = 1; i <= nstrong;i ++)
if(visit[i] == false)
flag = false;
if(flag == true)
{
printf("Yes\n");
}
else printf("No\n");
}
return 0;
}

```

posted on 2010-12-11 22:48 田兵 阅读(429) 评论(0)  编辑 收藏 引用 所属分类: 图论题

 < 2010年8月 >
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

• 随笔 - 65
• 文章 - 2
• 评论 - 17
• 引用 - 0

•

• 积分 - 23619
• 排名 - 667