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
題目：給定一個(gè)圖，問(wèn)你是否對(duì)于任意的定點(diǎn)對(duì)x,y，能找到一條從x到y(tǒng) 或從y到x的路徑，（滿(mǎn)足一條即可）；
類(lèi)型：弱連通分量。
解法：
這題花了很長(zhǎng)時(shí)間，至少花了兩個(gè)小時(shí)，到后來(lái)都想吐了，這讓我更惡心到了兩遍dfs求強(qiáng)連通分量的復(fù)雜。還好做出來(lái)了，雖然800+ms，還是挺爽的。
n： 1000， m： 6000
原來(lái)什么都沒(méi)想就開(kāi)始做，每次spfa(x,y)，嘗試從x找到一條道y的路徑，果斷TLE。其實(shí)肯定TLE，不知道當(dāng)時(shí)怎么想的。
這題先求強(qiáng)連通分量，縮點(diǎn)，形成一棵新的樹(shù)，這樣主要是為了利用一些性質(zhì)。若圖是弱連通的，縮點(diǎn)后的樹(shù)必須滿(mǎn)足一下性質(zhì)：
1，形成的是一棵樹(shù)：這是必須的。否則從一棵樹(shù)的點(diǎn)到另一棵樹(shù)無(wú)法到達(dá)。
2，這棵樹(shù)有且僅有一個(gè)點(diǎn)的入度是0, 如果有多個(gè)的話(huà)那么這些入度為0的點(diǎn)是不可以互相到達(dá)的。
3, 從這個(gè)入度為0的點(diǎn)進(jìn)行dfs，找到的是一條鏈，就是不會(huì)有分叉，如果有的話(huà)，則兩個(gè)分叉的點(diǎn)互相不可達(dá)。
（這點(diǎn)其實(shí)我不明白，應(yīng)該是找條最長(zhǎng)鏈的）
代碼超級(jí)亂：
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;
}