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 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;
        }

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


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


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

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜