缩点【洛谷P2860】 [USACO06JAN]冗余路径Redundant Paths

P2860 [USACO06JAN]冗余路径Redundant Paths

艹，明明想的是正解还想着hack。

丢人了丢人了。。。

还有注意判重。

数据大，在重构图的时候开一维桶。

code：

#include <iostream>

#include <cstdio>

using namespace std;

const int wx=200017;

inline int read(){

	int sum=0,f=1; char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}

	return sum*f;

}

int head[wx],dfn[wx],low[wx],belong[wx];

int size[wx],st[wx],in[wx];

int flag[1007][1007],t[wx];

int n,m,num,tot,top,col;

int ans;

struct e{

	int nxt,to;

}edge[wx*2];

void add(int from,int to){

	edge[++num].nxt=head[from];

	edge[num].to=to;

	head[from]=num;

}

void Tarjan(int u,int fa){

	dfn[u]=low[u]=++tot;

	st[++top]=u;

	for(int i=head[u];i;i=edge[i].nxt){

		int v=edge[i].to;

		if(v==fa)continue;

		if(!dfn[v]){

			Tarjan(v,u);

			low[u]=min(low[u],low[v]);

		}

		else if(!belong[v]){

			low[u]=min(low[u],dfn[v]);

		}

	}

	if(dfn[u]==low[u]){

		belong[u]=++col;

		size[col]++;

		while(st[top]!=u){

			belong[st[top]]=col;

			size[col]++; top--;

		}top--;

	}

}

int main(){

	n=read(); m=read();

	for(int i=1;i<=m;i++){

		int x,y;

		x=read(); y=read();

		add(x,y); add(y,x);

	}

	for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i,0);

	for(int u=1;u<=n;u++){

		for(int i=head[u];i;i=edge[i].nxt){

			int v=edge[i].to;

			if(belong[v]!=belong[u]&&!t[belong[v]])in[belong[v]]++,t[belong[v]]++;

		}

		for(int i=head[u];i;i=edge[i].nxt){

			int v=edge[i].to;

			t[belong[v]]=0;

		}

	}

	for(int i=1;i<=col;i++)ans+=(in[i]==1?1:0);

	if(ans&1)ans++;

	printf("%d\n",ans/2);

	return 0;

}