HDU 3836 Equivalent SetsTarjan+缩点)
HDU
2023-09-14 09:08:10 时间
Problem Description
To prove two sets A and B are equivalent, we can first prove A is a subset of B, and then prove B is a subset of A, so finally we got that these two sets are equivalent.
You are to prove N sets are equivalent, using the method above: in each step you can prove a set X is a subset of another set Y, and there are also some sets that are already proven to be subsets of some other sets.
Now you want to know the minimum steps needed to get the problem proved.
You are to prove N sets are equivalent, using the method above: in each step you can prove a set X is a subset of another set Y, and there are also some sets that are already proven to be subsets of some other sets.
Now you want to know the minimum steps needed to get the problem proved.
Input
The input file contains multiple test cases, in each case, the first line contains two integers N <= 20000 and M <= 50000.
Next M lines, each line contains two integers X, Y, means set X in a subset of set Y.
Next M lines, each line contains two integers X, Y, means set X in a subset of set Y.
Output
For each case, output a single integer: the minimum steps needed.
Sample Input
4 0 3 2 1 2 1 3
Sample Output
4 2HintCase 2: First prove set 2 is a subset of set 1 and then prove set 3 is a subset of set 1.
强联通缩点:加入几条边成强联通分量:设缩点后全部点中出度为0的点为d_1,入度为0点为d_2,则答案为max(d_1,d_2);
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<limits.h> typedef long long LL; using namespace std; #define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define REP( i , n ) for ( int i = 0 ; i < n ; ++ i ) #define CLEAR( a , x ) memset ( a , x , sizeof a ) const int maxn=20000+100; const int maxm=100000; struct node{ int u,v; int next; }e[maxm]; int head[maxn],cntE; int DFN[maxn],low[maxn]; int s[maxm],top,index,cnt; int belong[maxn],instack[maxn]; int in[maxn],out[maxn]; int n,m; void init() { top=cntE=0; index=cnt=0; CLEAR(DFN,0); CLEAR(head,-1); CLEAR(instack,0); // CLEAR(belong,0); } void addedge(int u,int v) { e[cntE].u=u;e[cntE].v=v; e[cntE].next=head[u]; head[u]=cntE++; } void Tarjan(int u) { DFN[u]=low[u]=++index; instack[u]=1; s[top++]=u; for(int i=head[u];i!=-1;i=e[i].next) { int v=e[i].v; if(!DFN[v]) { Tarjan(v); low[u]=min(low[u],low[v]); } else if(instack[v]) low[u]=min(low[u],DFN[v]); } int v; if(DFN[u]==low[u]) { cnt++; do{ v=s[--top]; belong[v]=cnt; instack[v]=0; }while(u!=v); } } void work() { REPF(i,1,n) if(!DFN[i]) Tarjan(i); if(cnt<=1) { puts("0"); return ; } CLEAR(in,0); CLEAR(out,0); for(int i=0;i<cntE;i++) { int u=e[i].u,v=e[i].v; if(belong[u]!=belong[v]) in[belong[v]]++,out[belong[u]]++; } int d_1=0,d_2=0; REPF(i,1,cnt) { if(!in[i]) d_1++; if(!out[i]) d_2++; } printf("%d\n",max(d_1,d_2)); } int main() { int u,v; while(~scanf("%d%d",&n,&m)) { init(); for(int i=0;i<m;i++) { scanf("%d%d",&u,&v); addedge(u,v); } work(); } return 0; }
相关文章
- HDU 1556-差分数组和线段树的对比分析-Color the ball
- hdu 3980 Paint Chain(SG函数)
- HDU 3336 KMP算法中对next数组的理解「建议收藏」
- HDU P3341 Lost’s revenge 题解+数据生成器
- hdu 3336 Count the string(kmp应用)
- hdu 3336 Count the string 用心写的题解
- hdu 1142_hdu1001
- HDU 3336 Count the string 解题报告
- [ACM] HDU 1006 解题报告
- H - Partial Tree HDU - 5534 【 完全背包 】
- HDU-2084 数塔
- 敌兵布阵(HDU 1166)
- I Hate It (HDU 1754)
- 校庆神秘建筑(HDU 1411)
- 还是畅通工程(HDU 1233)
- Friend-Graph (HDU 6152)2017中国大学生程序设计竞赛 - 网络选拔赛
- CaoHaha's staff (HDU 6154)(2017中国大学生程序设计竞赛 - 网络选拔赛)
- Oil Deposits (HDU - 1241 )(DFS思路 或者 BFS思路)
- 畅通工程续(HDU 1874)(简单最短路)
- Drainage Ditches (HDU - 1532)(最大流)
- Ancient Go ( HDU - 5546 ) ( BFS 搜索是否相连)
- 统计难题 【 HDU - 1251 】【 字典树 】
- Phone List 【 HDU - 1671 】 【 字典树判断是否存在前缀 】
- A * B Problem Plus【HDU 1402】 【FFT求高精度乘法】
- Bone Collector HDU - 2602【 01 背包 】