若A喜欢B则连一条边,求强联通分块,设出度为零的块数为C,若C>1则误解,C=1则输出块数
const int N = 10010, M = 50010; struct Edge { int v; Edge *Next; Edge() {} Edge(int _v, Edge *_Next) : v(_v), Next(_Next) {} } *Fir[N]; int n, m; inline void Ins(int u, int v) { Fir[u] = new Edge(v, Fir[u]); } inline void Input() { scanf("%d%d", &n, &m); For(i, 1, n) Fir[i] = NULL; For(i, 1, m) { int u, v; scanf("%d%d", &u, &v), Ins(u, v); } } int dfn[N], low[N], belong[N], tot, T; bool Instack[N]; int Out[N]; stack<int> sta; inline void tarjan(int x) { dfn[x] = low[x] = ++T, sta.push(x), Instack[x] = 1; for(Edge *Tab = Fir[x]; Tab != NULL; Tab = Tab->Next) { int v = Tab->v; if(dfn[v] == -1) { tarjan(v); low[x] = min(low[x], low[v]); } else if(Instack[v]) low[x] = min(low[x], dfn[v]); } if(dfn[x] == low[x]) { ++tot; while(sta.top() != x) { int v = sta.top(); belong[v] = tot, sta.pop(), Instack[v] = 0; } belong[x] = tot, Instack[x] = 0, sta.pop(); } } inline void Solve() { // rebuild clr(dfn, 255), clr(Instack, 0), tot = T = 0; while(sz(sta)) sta.pop(); For(i, 1, n) if(dfn[i] == -1) tarjan(i); // Check For(i, 1, tot) Out[i] = 0; For(i, 1, n) for(Edge *Tab = Fir[i]; Tab != NULL; Tab = Tab->Next) { int v = Tab->v; if(belong[v] ^ belong[i]) { Out[belong[i]] = 1; break; } } int Which = -1, Check = 0; For(i, 1, tot) if(!Out[i]) { if(!Check) Which = i, Check = 1; else if(Check) { Which = -1; break; } } int Ans = 0; For(i, 1, n) Ans += (belong[i] == Which); printf("%d\n", Ans); } int main() { #ifndef ONLINE_JUDGE SETIO("1051"); #endif Input(); Solve(); return 0; }
相关推荐
BZOJ原题-BZOJP1000-P2000的题目,下载后可以离线做题。
八中OJ,又简作BZOJ,以原题巨多而著称,该数据为BZOJ上的1000-1109和1130-1139的测试数据节点,没有题目,有需要题目的可以到https://hydro.ac/d/bzoj/p网站查找对应的题目。
By Hyt 数据结构 1. 线段树练习 X 3 CodeVS1080~1082 ... 受欢迎的牛 强联通分量 BZOJ1051 6. 部落划分 二分+最小生成树 BZOJ1821 7. 最长路径 最短路 BZOJ1295 8. 社交网络 Floyd 变种 BZOJ1491 9. 抢掠计划 最短路+图
「BZOJ1053」反素数/「Violet5」樱花 详细题解
BZOJ原题-BZOJP3001-P4000的题目,下载后可以离线做题。
bzoj部分数据.
BZOJ3230相似子串的测试数据,希望能够帮到大家。
BZOJ原题-BZOJP2001-P3000的题目,下载后可以离线做题。
BZOJ网站镜像,对于经常挂掉的BZOJ真是刷题必备啊!
BZOJ原题-BZOJP4001-P4406的题目,下载后可以离线做题。
BZOJ平台全部代码,解压到一个文件夹在打开使用。BZOJ平台全部代码,解压到一个文件夹在打开使用。
bzoj1878数据(莫队)详细题解:http://blog.csdn.net/boyxiejunboy/article/details/50611972
题解 , 文档 , 资料 BZOJ 泡泡堂
BZOJ省选十连测题面,只有题面!!!!!,请自行到BZOJ上进行提交,上传目的是提供离线的一个题目
ZOJCH是BZOJ题库的离线版
CreationAugust 的BZOJ代码合集 【Written by CreationAugust】
八中OJ所有题目
#BZOJ Problem Rankrank.cpp 程序文件data.dat bzoj题库数据done.dat AC过的题,初始可以把所有A过的题粘进去,正常退出的话自动维护。black.dat 黑名单。选题时会跳过。错题、神题、没题面、不想做等等。//Thank ...
本模板为 BZOJ3224:文艺平衡树 的源程序 含各种操作,旋转,插入,删除,求前驱,后继,查询值为x的数的排名,查询排名为k的数,求最大值,最小值……
bzoj FFT 的模版