问题描述
小 ww 生活在美丽的 ZZ 国. ZZ 国是一个有 nn 个城市的大国, 城市之间有 mm 条单向公路 (连 接城市 ii,jj 的公路只能从 ii 连到 jj). 城市 ii,jj 是友好城市当且仅当从城市 ii 能到达城市 jj 并 且从城市 jj 能到达城市 ii. 如果 kk 个城市两两互为友好城市, 那么我们称这 kk 个城市是友好 城市群, kk 为友好城市群的大小. 现在小 ww 想知道友好城市群的大小最大为多少, 你能告诉 他吗?
输入格式
第一行包含两个整数 nn 和 mm.
接下来 mm 行, 每行两个整数 ii 和 jj, 表示有从城市 ii 到城市 jj 的一条单向公路.
输出格式
共一行一个整数表示答案.
输入样例
- 10 12
- 3 7
- 1 2
- 4 5
- 7 10
- 10 8
- 6 8
- 2 1
- 3 8
- 10 3
- 6 8
- 7 3
- 4 1
输出样例
3
数据范围
对于 30% 的数据, n,m≤100n,m≤100
对于 80% 的数据, n≤1000,m≤100000n≤1000, m≤100000
对于 100% 的数据, n,m≤100000
题目分析
我定睛一看就把 Tarjan 这糟老头子拽出来了: 你特么又变着法子考我? 然后我就写完了代码, 下面献上.
代码实现
- #include<bits/stdc++.h>
- using namespace std;
- #define IL inline
- #define int long long
- #define RE register int
- #define N 100001
- int m,n,cnt,tim,ans;
- int head[N],dfn[N],low[N];
- stack<int>s;
- bitset<N>vis;
- struct aa{int v,next;}e[N<<1];
- IL void addedge(RE u,RE v){
- e[++cnt]=(aa){v,head[u]},head[u]=cnt;
- }IL void Tarjan(RE u){
- dfn[u]=low[u]=++tim,vis[u]=1,s.push(u);
- for (RE v,i=head[u];i;i=e[i].next){
- if (!dfn[v=e[i].v]) Tarjan(v),low[u]=min(low[u],low[v]);
- else if (vis[v]) low[u]=min(low[u],dfn[v]);
- }if (dfn[u]==low[u]){
- RE sum=0;
- do{++sum,vis[s.top()]=0,s.pop();}while(s.top()^u);
- ans=max(ans,sum);
- }
- }
- signed main(){
- // freopen("friend.in","r",stdin),freopen("friend.out","w",stdout);
- cin>>n>>m;
- for (RE i=1,u,v;i<=m;++i)
- cin>>u>>v,addedge(u,v);
- for (RE i=1;i<=n;++i) if (!dfn[i]) Tarjan(i);
- cout<<ans;
- }
代码分析
第一次交没有 AC, 因为我们的评测机爆炸了. 注意退栈的操作, 这一题不需要缩点, 大家学了网络流对 Tarjan 会懂得更多的.
我还要写什么呢, 睡觉去了, 整个晚上都没有和她联系, 有点孤单.
来源: http://www.bubuko.com/infodetail-2993333.html