poj 2762 Going from u to v or from v to u?

本文从WordPress迁移而来, 查看全部WordPress迁移文章

强连通分量

题意：给一个有向图，对于图中任意两个点u，v，如果从u能到v，或者，v能到u，则这对顶点是可行的，如果图中任意一对顶点都是可行的，可以输出Yes，否则输出No

这个的话，就不是裸的强连通分量了。思考一下，对于一个有向图而言，里面的强连通分量肯定满足题目的条件，因为强连通分量内是u可到v，而且，v可到u，所以我们第一步工作就是强连通分量缩点，变为一个DAG。对于这个DAG里面的任意两个点U,V，如果满足题目的条件，那么点U,V里面包含的原图的点也肯定是满足的

所以问题转化为怎么判断这个DAG是满足题目条件呢？其实判断很简单，就是看这个DAG里面有多少个点的入度为0，多少个点出度为0

如果DAG中，有2个或2个以上的点的入度为0，那么这个DAG就是No，因为这说明有两个点是无法“进去”的，没有点能“进去”U，也没有点能“进去”V，那么这两个点肯定互相不能“进去”，即到达

如果DAG中，有2个或2个以上的点的出度为0，那么这个DAG就是No，因为说明这两个点是无法“出去的”。

反证法，点U和V，它们出度都是0，假设它们满足题目条件，从U能到V，或者从V能到U

  1. 因为点U出度为0，所以无法“出去”，它肯定无法到达V
  2. 因为点V出度为0，所以无法“出去”，它肯定无法到达U
  3. 综上，点U无法到达V，点V无法到达点U，与假设矛盾，所以与题目不成立

那么什么最后一个问题，如果这个DAG，入度为0的点的个数 <= 1 , 出度为0的点的个数 <= 1 ， 它就一定Yes吗？

这个就比较容易想了，首先，1个DAG中，不可能所有点都有入度，即入度为0的点个数为0，是不可能发生的。同样的，可能所有点都有出度，即出度为0的点个数为0，是不可能发生的

那剩下的情况就是，1个点入度为0为u，1个点出度为0为v。这个图，呈现一个“橄榄形”。如果从点u走到点v，能经过所有的点，那么就是Yes，否则是No。因为无法经过所有的点的话，说明图中出现了“分叉”，这种“分叉”必定导致两个点互相不可达。而从u到v，经过所有点，其实就是把这个DAG变成了一条链，就是判断这个DAG是否存在一条链贯穿所有点

怎么判断链呢？可以转化为拓扑排序，或者DP最长路

拓扑：拓扑排序可能有多种结果，但是如果是一个最长链，结果则是唯一的，结果要唯一，其实就是从初始化开始，到后面的任何一次删弧入队操作，都是保证了每次都只有一个元素入队，即永远只有一个元素的入度为0，如果中途有一次出现了有两个点入度为0，那么其实代表出现了一种“分叉”

而且拓扑排序可以综合掉前面的情况，不需要特判DAG有几个点入度为0，出度为0，直接拓扑，在拓扑过程就已经判断了

DP：d[i]表示从i点（缩点后的i点）出发能走出的最长路，只要有一个点,d[i] = N , 说明这个点出发能走遍所有点，那么就是一个最长链，输出Yes，否则No

两个代码，前面部分都是相同的，即Tarjan缩点，只有后面不同，一个是int topsort(), 一个是int DP()

不过，这题的数据太弱了，一开始我想错了判断链的地方，写了个很简单的，后来测试错得一塌糊涂，但是POJ还是给了我AC…….

拓扑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//判断整个图是不是强连通分量
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
#define N 1010
#define M 6010

vector<int>ver[N];
vector<int>e[N];
stack<int>sta;
queue<int>que;
int n,tot;
int dfn[N],low[N],belong[N],inde[N],ins[N],dcnt,bcnt;

void dfs(int u)
{
    dfn[u] = low[u] = ++dcnt;
    sta.push(u); ins[u] = 1;
    for(int i=0; i<ver[u].size(); i++)
    {
        int v = ver[u][i];
        if(!dfn[v])
        {
            dfs(v);
            low[u] = min(low[u] , low[v]);
        }
        else if(ins[v])
            low[u] = min(low[u] , dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        bcnt++;
        while(true)
        {
            int x = sta.top();
            belong[x] = bcnt;
            ins[x] = 0;
            sta.pop();
            if(x == u) break;
        }
    }
}

int topsort()
{
    int count;
    while(!que.empty()) que.pop();
    count = 0;
    for(int i=1; i<=bcnt; i++)
        if(!inde[i])
        { count++; que.push(i);}
    if(count > 1) return 0; //入度为0的点超过1个
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        count = 0;
        for(int i=0; i<e[u].size(); i++)
        {
            int v = e[u][i];
            inde[v]--;
            if(!inde[v])
            { count++; que.push(v); }
        }
        if(count > 1) return 0; //删弧后，同时出现了两个点入度为0
    }
    return 1;
}

void solve()
{
    for(int i=1; i<=n; i++)
        if(!dfn[i])
            dfs(i);
    memset(inde,0,sizeof(inde));
    for(int i=1; i<=bcnt; i++) e[i].clear();

    for(int i=1; i<=n; i++)  
        for(int j=0; j<ver[i].size(); j++)
        {   //统计入度，并且给缩点后的DAG建图
            int u = belong[i];
            int v = belong[ver[i][j]];
            if(u != v) 
            { inde[v]++; e[u].push_back(v); } //重新建图
        }
    int ok = topsort(); //拓扑排序判断 
    if(ok) cout << "Yes" << endl;
    else   cout << "No" << endl;
}

int main()
{
    int cas;
    cin >> cas;
    while(cas--)
    {
        cin >> n >> tot;
        dcnt = bcnt = 0;
        while(!sta.empty()) sta.pop();
        for(int i=1; i<=n; i++)
        {
            ver[i].clear();
            dfn[i] = ins[i] = 0;
        }
        while(tot--)
        {
            int u,v;
            cin >> u >> v;
            ver[u].push_back(v);
        }
        solve();
    }
    return 0;
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
//判断整个图是不是强连通分量
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
#define N 1010
#define M 6010

vector<int>ver[N];
vector<int>e[N];
stack<int>sta;
queue<int>que;
int n,tot;
int dfn[N],low[N],belong[N],ins[N],d[N],dcnt,bcnt;

void dfs(int u)
{
    dfn[u] = low[u] = ++dcnt;
    sta.push(u); ins[u] = 1;
    for(int i=0; i<ver[u].size(); i++)
    {
        int v = ver[u][i];
        if(!dfn[v])
        {
            dfs(v);
            low[u] = min(low[u] , low[v]);
        }
        else if(ins[v])
            low[u] = min(low[u] , dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        bcnt++;
        while(true)
        {
            int x = sta.top();
            belong[x] = bcnt;
            ins[x] = 0;
            sta.pop();
            if(x == u) break;
        }
    }
}

void dp(int u)
{
    if(d[u] != -1) return ;
    d[u] = 1;
    for(int i=0; i<e[u].size(); i++)
    {
        int v = e[u][i];
        dp(v);
        if(d[v] + 1 > d[u]) d[u] = d[v] + 1;
    }
}

int DP()
{
    memset(d,-1,sizeof(d));
    for(int i=1; i<=bcnt; i++)
        if(d[i] == -1)
        {
            d[i] = 1;
            for(int k=0; k<e[i].size(); k++)
            {
                int j = e[i][k];
                dp(j);
                if(d[j] + 1 > d[i]) d[i] = d[j] + 1;
            }
            if(d[i] >= bcnt) return 1;
        }
        else if(d[i] >= bcnt) return 1;
    return 0;
}

void solve()
{
    for(int i=1; i<=n; i++)
        if(!dfn[i])
            dfs(i);

    for(int i=1; i<=bcnt; i++) e[i].clear();

    for(int i=1; i<=n; i++)  
        for(int j=0; j<ver[i].size(); j++)
        {   //统计入度，并且给缩点后的DAG建图
            int u = belong[i];
            int v = belong[ver[i][j]];
            if(u != v) e[u].push_back(v);  //重新建图
        }
    //int ok = topsort(); //拓扑排序判断 
    int ok = DP();
    if(ok) cout << "Yes" << endl;
    else   cout << "No" << endl;
}

int main()
{
    int cas;
    cin >> cas;
    while(cas--)
    {
        cin >> n >> tot;
        dcnt = bcnt = 0;
        while(!sta.empty()) sta.pop();
        for(int i=1; i<=n; i++)
        {
            ver[i].clear();
            dfn[i] = ins[i] = 0;
        }
        while(tot--)
        {
            int u,v;
            cin >> u >> v;
            ver[u].push_back(v);
        }
        solve();
    }
    return 0;
}