Codeforces - 1020B Badge（找环）

题意：

　　以每个点为起点，找到第一个出现两次的点

解析：

　　我是先找出来所有的环  环上的点找出来的肯定是自己 bz[i]  = i;

然后去遍历不在环上的点j  如果通过这个点找到一个已经标记的的点i  那么bz[j] = bz[i];

行吧。。。其实直接暴力 就几行代码。。。真是的。。。过分。。。。我真是垃圾啊。。啦啦啦。。。呸。。

#include <bits/stdc++.h>

using namespace std;

const int maxn = , INF = 0x7fffffff;

vector<int> G[maxn];

vector<int> f;

int vis[maxn], bz[maxn], a[maxn];

int s, t, tmp;

void dfs1(int u)

{

    vis[u] = ;

    for(int i=; i<G[u].size(); i++)

    {

        int v = G[u][i];

        if(!vis[v])

            dfs1(v);

        else if(u != v)

        {

            s = v;

            tmp = u;

            return;

        }

        else

        {

            bz[v] = v;

            return;

        }

    }

    if(u == s)

        t = tmp;

}

void dfs2(int u)

{

    bz[u] = u;

    if(u == t) return;

    for(int i=; i<G[u].size(); i++)

        dfs2(G[u][i]);

}

int dfs3(int u)

{

    if(bz[u]) return bz[u];

    for(int i=; i<G[u].size(); i++)

        return dfs3(G[u][i]);

}

int main()

{

    int n, v;

    cin>> n;

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

    {

        cin>> a[i];

        G[i].push_back(a[i]);

    }

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

        if(!vis[i])

        {

            s = t = tmp = INF;

            dfs1(i);

            if(s != INF && t != INF)

                dfs2(s);

        }

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

    {

        if(bz[i]) continue;

        else

            bz[i] = dfs3(i);

    }

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

        cout<< bz[i] << " ";

    cout<<endl;

    return ;

}