codeforces 129 B. Students and Shoelaces

Posted by 111qqz on Saturday, December 5, 2015

TOC

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;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付