CodeForces 131D【图特性+BFS】

题意：

只有一个环，然后环都是0（环缩点相当于树的根），然后其余的输出到根的距离

思路：

可以从度为1的 开始搜 把那些分支全标记掉，然后再取没有标记掉的，BFS一下搞出距离。

具体这个标记：

倒着搜这样肯定没有多对一，标记掉度等于2的那些点就好了，度>2的要减减，而且环里的点的度不可能搜到度 = 2 因为环=点的度为2，他又连出一条边 度=3。

后话：

这种n个点 n条边/n-1条边的题都是套路了，要仔细考虑图特性：点的度（出度，入度），怎么搜（顺着搜，倒着搜，BFS好写还是DFS好写）

但是一旦确定思路，要多举反例，谨防入坑！！

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=3e3+10;

struct asd{

    int to;

    int next;

};

asd e[N*2];

int head[N],tol;

int n,m;

int pre[N];

bool vis[N],used[N];

void add(int u,int v)

{

	e[tol].to=v;

	e[tol].next=head[u];

	head[u]=tol++;

}

void solve1()

{

	queue<int>q;

	for(int i=1;i<=n;i++)

	{

		if(pre[i]==1)

		{

			q.push(i);

			vis[i]=true;

		}

	}

	while(!q.empty())

	{

		int u=q.front();q.pop();

		for(int i=head[u];~i;i=e[i].next)

		{

			int v=e[i].to;

			if(vis[v]) continue;

			if(pre[v]==2)

			{

				vis[v]=true;

				q.push(v);

			}

			pre[v]--;

		}

	}

}

int ans[N];

void solve2()

{

	queue<int>q;

	for(int i=1;i<=n;i++)

		if(!vis[i])

		{

			ans[i]=0;

			used[i]=true;

			q.push(i);

		}

	while(!q.empty())

	{

		int u=q.front();q.pop();

		for(int i=head[u];~i;i=e[i].next)

		{

			int v=e[i].to;

			if(used[v]) continue;

			ans[v]=ans[u]+1;

			used[v]=true;

			q.push(v);

		}

	}

}

int main()

{

	int u,v;

	scanf("%d",&n);

	tol=0;

	memset(head,-1,sizeof(head));

	for(int i=0;i<n;i++)

	{

		scanf("%d%d",&u,&v);

		add(u,v);

		add(v,u);

		pre[u]++;

		pre[v]++;

	}

	solve1();

	solve2();

	for(int i=1;i<=n;i++)

		printf("%d ",ans[i]);

	return 0;

}

/*

6

1 2

3 4

6 4

2 3

1 3

3 5

6

1 2

2 3

3 1

1 4

4 5

4 6

*/