记录编号	39496	评测结果	AAAAAAAAAAAAAAAAA
题目名称	[USACO Jan06]Redundant Paths	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2012-07-12 14:37:59	内存使用	0.55 MiB

#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("rpathsa.in");
ofstream fout("rpathsa.out");
int F,R,Color[6000],Cn,Bn,degree[6000],target,A[6000],deep[6000];
bool visited[6000];
string S[6000];
class Node
{
public:
	int Name;bool del;
	Node *Prev,*next,*reverse;
	Node()
	{
		del=false;
	}
}*last[6000],*nlast[6000];
class Bridge
{
public:
	Node *rec;
	int from,to;
}bridge[6000];
Node *ADD(int u,int v)
{
Node *p=new Node;
	p->Name=v;
	p->Prev=last[u];
	if(last[u])
		last[u]->next=p;
	last[u]=p;
	last[u]->next=NULL;
	return last[u];
}

void Initialize()
{
int i,U,V;
	fin>>F>>R;
	for(i=1;i<=F;i++)
	{
		S[i]="White";
		last[i]=NULL;
	}
	for(i=1;i<=R;i++)
	{
		Node *p1,*p2;
		fin>>U>>V;
		p1=ADD(U,V);
		p2=ADD(V,U);
		p1->reverse=p2;
		p2->reverse=p1;
	}
}

void Floodfill(int pos)
{
Node *p;
	for(p=last[pos];p;p=p->Prev)
		if(!visited[p->Name] && !p->del)
		{
			visited[p->Name]=true;
			Color[p->Name]=Cn;
			Floodfill(p->Name);
		}
}

void nAdd(int u,int v)
{
Node *p=new Node;
	p->Name=v;
	p->Prev=last[u];
	nlast[u]=p;
}

void MakeNew()
{
int i;
	for(i=1;i<=Cn;i++)
		nlast[i]=NULL;
	for(i=1;i<=Bn;i++)
	{
		nAdd(Color[bridge[i].from],Color[bridge[i].to]);
		nAdd(Color[bridge[i].to],Color[bridge[i].from]);
		degree[Color[bridge[i].from]]++;
		degree[Color[bridge[i].to]]++;
	}
}
void Fin()
{
int i;
	for(i=1;i<=Cn;i++)
		if(degree[i]==1)
			target++;
}
void GetBridge(int pos,int d,int father,Node *sd)
{
Node *p;int tot=0;
d++;
S[pos]="Gray";
	deep[pos]=d;A[pos]=d;
	for(p=last[pos];p;p=p->Prev)
	{
		if(p->reverse!=sd)
		{
			if(S[p->Name]=="White")
				GetBridge(p->Name,d,pos,p);
			
			tot++;A[pos]=min(A[pos],A[p->Name]);
			if(A[p->Name]>deep[pos] && !p->del)
			{
				Bn++;
				bridge[Bn].rec=p;
				bridge[Bn].from=pos;
				bridge[Bn].to=p->Name;
				p->del=true;
				p->reverse->del=true;
			}
		}
	}
	S[pos]="Black";
}

void Solve()
{
int i;
	GetBridge(1,0,0,NULL);
	Cn=1;
	for(i=1;i<=F;i++)
		if(!visited[i])
		{
			visited[i]=true;
			Color[i]=Cn;
			Floodfill(i);
			Cn++;
		}
	MakeNew();
	Fin();
	fout<<(target+1)/2<<endl;
}

int main()
{
	Initialize();
	
	Solve();
	
	fin.close();
	fout.close();
	return 0;
}