「图论练习」medium
hzwer蒟蒻刚刚学了点图论，现在他面对一张无向连通图
他想问你
最少添加多少条边，使得任意两点之间有两条无公共边的路（可以有公共点）
输入格式
第一行n，m，n个点m条边
接下来m行，每行u，v
表示u到v之间有一条无向边（可能重复描述一条边）
输出格式
一行，答案
样例输入
5 5
1 2
2 3
3 4
4 5
4 5
样例输出
1
数据范围
20%的数据N<=20, M<=50
40%的数据N<=2000,M<=2000
70%的数据N<=20000,M<=20000
100%的数据N<=50000,M<=50000
题解
缩点后，ans=（度为1的连通块个数+1）/2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<cstdio> #include<cmath> #include<cstring> #include<iostream> #define ll long long using namespace std; int read() { int x=0;char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,m,cnt=1,top,scc,ind; int last[50005],low[50005],dfn[50005],q[50005],bl[50005]; int d[50005]; bool inq[50005]; struct edge{ int to,next; }e[100005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt; } void tarjan(int x,int fa) { low[x]=dfn[x]=++ind; q[++top]=x;inq[x]=1; for(int i=last[x];i;i=e[i].next) if(i!=(fa^1)) { if(!dfn[e[i].to]) { tarjan(e[i].to,i); low[x]=min(low[x],low[e[i].to]); } else if(inq[e[i].to]) low[x]=min(low[x],dfn[e[i].to]); } if(low[x]==dfn[x]) { scc++; int now=0; while(x!=now) { now=q[top--];inq[now]=0; bl[now]=scc; } } } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); insert(u,v); } for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i,0); for(int x=1;x<=n;x++) for(int i=last[x];i;i=e[i].next) if(bl[x]!=bl[e[i].to]) d[bl[e[i].to]]++; int sum=0; for(int i=1;i<=scc;i++) if(d[i]==1)sum++; printf("%d\n",(sum+1)/2); return 0; } |
计数器 9364475
OI 课件=>
OI 课件=>
为什么无向图可以用这种Tarjan。。。不应该用low[to
]>=dfn 
的那个吗。。还是说两种是一样的？
无向图去掉回路不是和有向图一样么
巨大题目旁边的这些图片都是哪里来的啊，好好看
某同学提供