首页 > 代码库 > BZOJ 1116: [POI2008]CLO
BZOJ 1116: [POI2008]CLO
1116: [POI2008]CLO
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 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
1 2
2 3
1 3
3 4
1 4
Sample Output
TAK
上图给出了一种连接方式.
上图给出了一种连接方式.
HINT
Source
分析
发现,如果一个联通块内存在至少一个环,则这个联通块一定可以满足要求。而不同联通块之间的点,互相之间没有任何影响。
所以需要做的就是在每个联通块内寻找是否存在至少一个环,并查集即可。
代码
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 }
@Author: YouSiki
BZOJ 1116: [POI2008]CLO
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。