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