首页 > 代码库 > BZOJ 1116: [POI2008]CLO

BZOJ 1116: [POI2008]CLO

1116: [POI2008]CLO

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 922  Solved: 514
[Submit][Status][Discuss]

Description

Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 你要把其中一些road变成单向边使得:每个town都有且只有一个入度

Input

第一行输入n m.1 <= n<= 100000,1 <= m <= 200000 下面M行用于描述M条边.

Output

TAK或者NIE 常做POI的同学,应该知道这两个单词的了...

Sample Input

4 5
1 2
2 3
1 3
3 4
1 4
技术分享

Sample Output

TAK
技术分享
上图给出了一种连接方式.

HINT

 

Source

 
[Submit][Status][Discuss]

 

分析

发现,如果一个联通块内存在至少一个环,则这个联通块一定可以满足要求。而不同联通块之间的点,互相之间没有任何影响。

所以需要做的就是在每个联通块内寻找是否存在至少一个环,并查集即可。

代码

技术分享
 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <iostream>
 6 #include <algorithm>
 7 
 8 using namespace std;
 9 
10 #define N 100005
11 #define M 200005
12 
13 int n, m;
14 
15 int fa[N];
16 int fg[N];
17 
18 int stk[N];
19 
20 int find(int u)
21 {
22     int tot = 0;
23     
24     while (u != fa[u])
25         stk[++tot] = u, u = fa[u];
26         
27     while (tot)
28         fa[stk[tot--]] = u;
29     
30     return u;
31 }
32 
33 signed main(void)
34 {
35     scanf("%d%d", &n, &m);
36     
37     for (int i = 1; i <= n; ++i)
38         fa[i] = i, fg[i] = false;
39         
40     for (int i = 1; i <= m; ++i)
41     {
42         int x; scanf("%d", &x);
43         int y; scanf("%d", &y);
44         
45         int fx = find(x);
46         int fy = find(y);
47         
48         if (fx ^ fy)
49         {
50             fa[fy] = fx;
51             fg[fx] |= fg[fy];
52         }
53         else
54             fg[fx] |= true;
55     }
56     
57     for (int i = 1; i <= n; ++i)
58         if (!fg[find(i)])
59             return puts("NIE"), 0;
60             
61     return puts("TAK"), 0;
62 }
BZOJ_1116.cpp

 

@Author: YouSiki

BZOJ 1116: [POI2008]CLO