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

缘起

日常浪费生命 poj 2762 Going from u to v or from v to u?

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给你一张有向图，要你回答是否图中任何两点u、v都存在一条u到v的路径亦或是v到u的路径.

【输入】
多样例. 每个样例开始于两个正整数n和m(0 < n < 1001,m < 6000). n是顶点的个数, m是弧的条数
然后是m行，每行包含两个正整数u,v表示u到v的弧.

【输出】
对于每个样例，如果是单向连通的, 则输出 "Yes", 否则输出"No"

【样例输入】
1
3 3
1 2
2 3
3 1

【样例输出】
Yes

【限制】
2s

裸的scc（但是比较综合的图论题）. 只需要保证所有scc的tarjan缩点重构DAG(一定是DAG，不可能有环)之后的拓扑序唯一即可. 如果是唯一的, 则回答 Yes, 否则回答No

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
using namespace std;
//#define LOCAL

int n,m, head[1005],head1[1005], cnt,cnt1, sccnum,t, low[1005], timestamp[1005], belong[1005], indeg[1005];
vector<int> scc[1005];
stack<int> s;
bool ins[1005];

struct Arc
{
	int from, to, nxt;
}g[6005],g1[6005];

void addArc(int a, int b)
{
	g[cnt].from = a, g[cnt].to = b, g[cnt].nxt = head[a];
	head[a] = cnt++;
}

void dfs(int i)
{
	timestamp[i] = low[i] = ++t;
	s.push(i), ins[i] = true;
	for (int h = head[i],to; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		if (!timestamp[to])
		{
			dfs(to);
			low[i] = min(low[i], low[to]);
		}
		else if (ins[to])
		{
			low[i] = min(low[i], low[to]);
		}
	}
	if (timestamp[i] ==low[i])
	{
		sccnum++;
		int j;
		do 
		{
			j = s.top(),s.pop(), ins[j] = false;
			scc[sccnum].push_back(j), belong[j] = sccnum;
		} while (j!=i);
	}
}

void tarjan()
{
	for (int i = 1; i<=n; i++)
	{
		if (!timestamp[i])
		{
			dfs(i);
		}
	}
}

void addArc1(int from, int to)
{
	g1[cnt1].from = from, g1[cnt1].to = to, g1[cnt1].nxt = head1[from];
	head1[from] = cnt1++;
}

void rebuild() // 缩点重构DAG
{
	for (int i = 0, from, to; i<cnt; i++)
	{
		from = belong[g[i].from], to = belong[g[i].to]; // 原弧g[i]两端点所属的scc
		if (from!=to)
		{
			addArc1(from, to);
			indeg[to]++;
		}
	}
}

bool topsort() // 注意, 缩点后的图(sccnum个顶点)一定是DAG
{
	stack<int> ss;
	for (int i = 1; i<=sccnum;i++)
	{
		if (!indeg[i])
		{
			ss.push(i);
		}
	}
	while(!ss.empty())
	{
		if (ss.size()>1) // 拓扑序不唯一
		{
			return false;
		}
		int top = ss.top();
		ss.pop();
		for (int h = head1[top],to; ~h; h = g1[h].nxt)
		{
			to = g1[h].to;
			if (!--indeg[to])
			{
				ss.push(to);
			}
		}
	}
	return true; // 拓扑序唯一
}

int main() {

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		scanf("%d%d", &n, &m);
		memset(head, -1, sizeof(head));
		memset(head1, -1, sizeof(head));
		memset(timestamp,0,sizeof(timestamp));
		memset(low,0, sizeof(low));
		memset(ins, 0, sizeof(ins));
		memset(belong, 0, sizeof(belong));
		memset(indeg, 0, sizeof(indeg));
		for (int i = 1; i<=sccnum; i++)
		{
			scc[i].clear();
		}
		cnt = cnt1 = sccnum = t = 0;
		while(!s.empty())
		{
			s.pop();
		}
		while(m--)
		{
			int a,b;
			scanf("%d%d", &a,&b);
			addArc(a,b);
		}
		tarjan();
		rebuild();
		topsort()?puts("Yes"):puts("No");
	}
	return 0;
}

ac情况

Status Accepted
Time 329ms
Memory 376kB
Length 2450
Lang C++
Submitted 2019-09-08 20:29:13
Shared
RemoteRunId 20844147