aoj0508:String With Rings

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0508

解法

グラフがとても小さいので、全探索した。
具体的には、まず始点を決めてそのあとに深さ優先探索で全経路試した。

コード

#include<bits/stdc++.h>
using namespace std;

int N;
vector<int>G[100];

bool used[100];
int dfs(int pos){
    used[pos]=true;

    int ret=0;
    for(int i=0;i<G[pos].size();i++){
        int to=G[pos][i];
        if(used[to])continue;
        ret=max(ret,dfs(to));
    }
    used[pos]=false;

    return ret+1;
}

void solve(){
    fill_n(G,100,vector<int>());
    for(int i=0;i<N;i++){
        int a,b;cin>>a>>b;
        G[--a].push_back(--b);
        G[b].push_back(a);
    }

    int ma=0;

    for(int i=0;i<100;i++){
        fill_n(used,100,false);
        ma=max(ma,dfs(i));
    }
    cout<<ma<<endl;

}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    while(cin>>N,N)solve();
    return 0;
}