CFR 129 B. Students and Shoelaces ( DFS )

Problem - B - Codeforces
把度數和邊的變量維護好就很簡單。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 2;
const int MAXM = MAXN * MAXN / 2;

int n, m;
vector< int > G[ MAXN ];
int deg[ MAXN ], d_deg[ MAXN ];

void solve(){
    int cnt = 0;
    while( m ){
        int c = 0;
        for( int u = 1; u <= n; ++u )
            if( deg[ u ] == 1 ){
                for( int v : G[ u ] )
                    if( deg[ v ] )
                        ++d_deg[ v ], --deg[ u ],
                        --m;
                ++c;
            }
        if( c == 0 ) break;
        ++cnt;
        for( int u = 1; u <= n; ++u )
            deg[ u ] -= d_deg[ u ],
            d_deg[ u ] = 0;
    }
    printf("%d\n", cnt);
}

int main(){
    scanf("%d%d", &n, &m);
    for( int i = 0; i < m; ++i ){
        int u, v; scanf("%d%d", &u, &v);
        G[ u ].push_back( v );
        G[ v ].push_back( u );
        ++deg[ u ];
        ++deg[ v ];
    }
    solve();
    return 0;
}