BZOJ 1116: [POI2008]CLO
2024-10-10 19:59:31
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
1 2
2 3
1 3
3 4
1 4
Sample Output
TAK
上图给出了一种连接方式.
上图给出了一种连接方式.
HINT
Source
分析
发现,如果一个联通块内存在至少一个环,则这个联通块一定可以满足要求。而不同联通块之间的点,互相之间没有任何影响。
所以需要做的就是在每个联通块内寻找是否存在至少一个环,并查集即可。
代码
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> using namespace std; #define N 100005
#define M 200005 int n, m; int fa[N];
int fg[N]; int stk[N]; int find(int u)
{
int tot = ; while (u != fa[u])
stk[++tot] = u, u = fa[u]; while (tot)
fa[stk[tot--]] = u; return u;
} signed main(void)
{
scanf("%d%d", &n, &m); for (int i = ; i <= n; ++i)
fa[i] = i, fg[i] = false; for (int i = ; i <= m; ++i)
{
int x; scanf("%d", &x);
int y; scanf("%d", &y); int fx = find(x);
int fy = find(y); if (fx ^ fy)
{
fa[fy] = fx;
fg[fx] |= fg[fy];
}
else
fg[fx] |= true;
} for (int i = ; i <= n; ++i)
if (!fg[find(i)])
return puts("NIE"), ; return puts("TAK"), ;
}
BZOJ_1116.cpp
@Author: YouSiki
最新文章
- Android中的Touch事件
- VBS操作剪切板
- 清空form表单下所有的input值-------------jquery
- spring boot 拦截器
- MVC - Code First Migration Command line
- c#转义字符串中的所有正则特殊字符
- C++数组(指针)作为函数参数
- 在 Windows Azure 虚拟机中如何备份和还原 Windows 系统磁盘
- 转百度前辈的Trados使用心得
- 201521123087《Java程序设计》第12周学习总结
- JS数组添加删除
- [物理学与PDEs]第5章第2节 变形的描述, 应变张量 2.3 位移梯度张量与无穷小应变张量
- python中的包与模块
- 知识扩展——Git和GitHub的区别
- CentOS 6.5下Squid代理服务器的安装与配置
- Ubuntu下实现socks代理转http代理
- bzoj 1857
- js模拟实现哈希表
- 触摸事件MotionEvent
- bootstrap-datetimepicker年视图中endDate设置之后比正常时间提前两个月
热门文章
- offsetLeft与offsetTop详解
- java多线程系类:基础篇:09之interrupt()和线程终止方式
- 阿里云安装LNMP以及更改网站文件和MySQL数据目录
- mac 10.9.4下配置apache
- LeetCode:Minimum Depth of Binary Tree,Maximum Depth of Binary Tree
- int,long,unsigned的值范围
- Oracle 常用操作【01】修改、更新数据
- IIS W3SVC 无法启动1068错误的解决
- C语言strcat()函数:连接字符串
- Android 轻量级输入校验库:Fire Eye