codeforces 129 B. Students and Shoelaces

http://codeforces.com/contest/129/problem/B 题意：n个点。m条边。每一次会将图中度为1的点加入到等待队列中。然后一起删掉，记为一次操作。当删掉一个点的时候，与它相连的边也全部删掉。问一共做进行多少次操作。使得图中不再有度为1的点。 思路：重点是用开一个数组deg[i]记录点i的度。这样比用.size()高明太多。。因为我们并不需要知道具体删了哪条边。我们只要知道与点i相连的点的边数因为点i被删除而减少了1.

/* ***********************************************
Author :111qqz
Created Time :2015年12月05日 星期六 10时55分46秒
File Name :code/cf/problem/129B.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;



using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=105;
int n,m;
vector<int>edge[N];
int deg[N];
int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif
	ms(deg,0);
	scanf("%d %d",&n,&m);
	for ( int i = 0 ; i < m ; i++)
	{
	    int u,v;
	    scanf("%d %d",&u,&v);
	    edge[u].push_back(v);
	    edge[v].push_back(u);
	    deg[u]++;
	    deg[v]++;  //记录下度..比用.size()然后再去找边高明的多。。因为并不需要知道到底删了哪条边。
	}

	bool flag;
	int ans = 0 ;
	while (1)
	{
	    flag = false;
	    int tmp[N];
	    memcpy(tmp,deg,sizeof(deg));  //因为是先训斥，把当前所有的训斥完再一起T出去。
	    for ( int i = 1 ; i <= n ; i++)
	    {
		if (deg[i]==1)
		{
		    flag = true;
		    tmp[i]--;
		    for ( int j = 0 ; j < edge[i].size(); j++)
		    {
			int to = edge[i][j];
			tmp[to]--; //不需要知道断了和谁的联系，只需要知道连接的数目少了1就好了。
		    }

		}
	    }
	    if (!flag) break;
	    memcpy(deg,tmp,sizeof(tmp));
	    ans++;
	  //  puts("zzzzz");
	}
	printf("%d\n",ans);

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}