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