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 adj[MAXV][MAXV];
int adj_op[MAXV][MAXV];
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 ++)
if(!visit[adj[u][i]])dfs1(adj[u][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 ++)
if(!visit[adj_op[u][i]])dfs2(adj_op[u][i],nstrong);
}
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(adj,0,sizeof adj);
memset(f,0,sizeof f);
memset(adj_op, 0, sizeof (adj_op));
scanf("%d %d",&n, &m);
for(i = 0; i < m; i ++)
{
scanf("%d %d",&u, &v);
adj[u][0] ++;
adj[u][adj[u][0]] = v;
adj_op[v][0] ++;
adj_op[v][adj_op[v][0]] = u;
}
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++ )
if(sblg[i] != sblg[adj[i][j]])
{
in[sblg[adj[i][j]]] = true;
strong[sblg[i]][sblg[adj[i][j]]] = true;
}
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;
}