题解

55 条题解

  • 6
    @ 2017-10-25 11:39:04

    并查集求最短路
    把每个同学看成一个点,信息的传递就是在他们之间连有向边,游戏轮数就是求最小环。
    图论求最小环,我在里面看到了并查集。
    假如说信息由A传递给B,那么就连一条由A指向B的边,同时更新A的父节点,A到它的父节点的路径长也就是B到它的父节点的路径长+1。
    这样我们就建立好了一个图,之后信息传递的所有环节都按照这些路径。游戏结束的轮数,也就是这个图里最小环的长度。
    如果有两个点祖先节点相同,那么就构成一个环,环的长度为两点到祖先节点的距离之和+1。

    #include<cstdio>
    #include<iostream>
    using namespace std;
    int f[200002],d[200002],n,minn,last;   //f保存祖先节点,d保存到其祖先节点的路径长。 
    int fa(int x)
    {
        if (f[x]!=x)                         //查找时沿途更新祖先节点和路径长。 
        {
            int last=f[x];                     //记录父节点(会在递归中被更新)。 
            f[x]=fa(f[x]);                     //更新祖先节点。 
            d[x]+=d[last];                     //更新路径长(原来连在父节点上)。 
        }
        return f[x];
    }
    void check(int a,int b)
    {
        int x=fa(a),y=fa(b);                 //查找祖先节点。 
        if (x!=y) {f[x]=y; d[a]=d[b]+1;}     //若不相连,则连接两点,更新父节点和路径长。 
        else minn=min(minn,d[a]+d[b]+1);     //若已连接,则更新最小环长度。 
        return;
    }
    int main()
    {
        int i,t;
        scanf("%d",&n);
        for (i=1;i<=n;i++) f[i]=i;           //祖先节点初始化为自己,路径长为0。 
        minn=0x7777777;
        for (i=1;i<=n;i++)
        {
            scanf("%d",&t);
            check(i,t);                        //检查当前两点是否已有边相连接。 
        }
        printf("%d",minn);
        return 0;
    }
    
  • 4
    @ 2016-07-07 21:39:56

    思路:**并查集**判断最小环。输入的每一条信息路径可以看作一条有向边,**答案则是所有环中最小环的长度**。用并查集一边合并图,**一边检查新增边的两点是否已经在一个root中。如果为真,则增加此边后就会成环。**此时环的大小为dis[x] + dis[y] + 1,即为所求答案的一个值。若为假则增加这条边。
    维护并查集时引入了一个dis[]数组,记录**此节点到根节点**的距离(途径边数),初始化都为0(自己到自己,不存在边)。若根节点被并入成为另一个子图的儿子,**它的子节点的dis在Find的时候被更新**。若成功新并入一条边,新边**出发点的dis在Union的时候被更新**。
    ```c++
    #include <iostream>
    using namespace std;

    int root[200001], dis[200001] = {0};
    int n, mindis = 9999999;

    void Init()
    {
    for(int i = 1; i <= n; i++)
    root[i] = i;
    return;
    }
    int Find(int x)
    {
    if(x == root[x])
    return x;
    int tempRoot = root[x];
    root[x] = Find(root[x]);
    dis[x] += dis[tempRoot];
    return root[x];
    }
    bool Union(int x, int y)
    {
    int xRoot = Find(x);
    int yRoot = Find(y);
    if(xRoot != yRoot) {
    root[xRoot] = yRoot;
    dis[x] = dis[y] + 1;
    return true;
    } else {
    mindis = min(mindis, dis[x] + dis[y] + 1);
    return false;
    }
    }

    int main()
    {
    cin >> n;
    Init();
    int ty;
    for(int i = 1; i <= n; i++) {
    cin >> ty;
    Union(i, ty);
    }
    cout << mindis << endl;
    return 0;
    }

    [这篇并查集教程写的还不错,大家可以看看。](http://m.blog.csdn.net/article/details?id=37968863)
    最后庆祝自己第一次尝试NOIP原题兼第一次使用VIJOS一次性AC~~~
    
  • 3
    @ 2017-10-16 15:12:12

    tarjan缩点,注意判断是否大小为1。

    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #define LL long long
    using namespace std;
    template <class _T> inline void read(_T &_x){
        int _t;bool _flag=0;
        while((_t=getchar())!='-'&&(_t<'0'||_t>'9'));
        if(_t=='-')_flag=1,_t=getchar();_x=_t-'0';
        while((_t=getchar())>='0'&&_t<='9')_x=_x*10+_t-'0';
        if(_flag)_x=-_x;
    }
    const int maxn=2e5+5;
    int n,cnt,x,top,idx,num[maxn],S[maxn],f[maxn],low[maxn],dfn[maxn],head[maxn],ans=0x3f3f3f3f;
    bool ins[maxn];
    struct edge{
        int v,nxt;
    }d[maxn];
    inline void add(int a,int b){
        d[++cnt].v=b;d[cnt].nxt=head[a];head[a]=cnt;
    }
    int find(int x){
        return x==f[x]? x:f[x]=find(f[x]);
    }
    void tj(int u){
        int v;
        dfn[u]=low[u]=++idx;
        S[++top]=u;ins[u]=1;
        for(int i=head[u];i;i=d[i].nxt){
            v=d[i].v;
            if(!dfn[v]){
                tj(v);
                low[u]=min(low[v],low[u]);
            }
            else if(ins[v])low[u]=min(dfn[v],low[u]);
        }
        if(dfn[u]==low[u]){
            while(u!=v){
                v=S[top--];
                ins[v]=0;
                int f1=find(u),f2=find(v);
                f[f2]=f1;
                if(f1!=f2)num[f1]+=num[f2];
            }
        }
    }
    int main(){
        read(n);
        for(int i=1;i<=n;i++){
            read(x);
            add(i,x);
        }
        for(int i=1;i<=n;i++)f[i]=i,num[i]=1;
        for(int i=1;i<=n;i++)if(!dfn[i])tj(i);
        for(int i=1;i<=n;i++){
            int tmp=num[find(i)];
            if(tmp!=1)ans=min(ans,tmp);
        }
        printf("%d",ans);
        return 0;
    }
    
  • 2
    @ 2017-10-28 19:14:05

    我用的是类似拓补排序的方法将没有在环中的结点删除
    然后再求每个环的大小

    #include<stdio.h>
    #include<string.h>
    int n,t[200010],d[200010]; //t[i]保存输入数据(即传递目标),d保存入度(即被多少人作为传递目标) 
    int main(){
        scanf("%d",&n);
        int i,k,c,temp,ans=999999;
        memset(d,0,sizeof(d));
        for (i=1;i<=n;i++){
            scanf("%d",&t[i]);
            d[t[i]]++;  //输入数据,然后子结点入度+1 
        }
        for(i=1;i<=n;i++){  //删除所有不在环中的点(从入度为0的点开始删,删了之后判断其子结点是否入度为0,是就继续删除) 
            if(t[i]==0) continue; //t[i]=0就是这个结点已经被删除了 
            k=i;
            while(d[k]==0){//入度为0就删除 
                temp=t[k];
                t[k]=0;
                k=temp;
                d[k]--;//删除之后它的子结点入度-1,然后继续判断直到有环的结点(有环的结点肯定有其他父结点) 
                
            }
        }
        for(i=1;i<=n;i++){//求最小环 
            if(t[i]==0)continue; 
            k=t[i];c=1;t[i]=0;//c来保存当前环的大小,k作为指针一直往子结点走直到回到原点 
            while(k!=i){
                temp=k;k=t[k];t[temp]=0;
                c++;
            }
            if(ans>c) ans=c;
        }
        printf("%d",ans);
        return 0;
    }
    
    
  • 1
    @ 2018-08-20 09:14:55
    /*
    这道题很明显就是
    在一个只有n条有向边的图中,每个结点出度为1,求一个包含节点数最少的环
    1.Tarjan算法求所有强连通分量,
    然后再求出所有含结点个数不为1的强连通分量的结点个数的最小值
    2.先把入度为0的点删除,然后把这个点指向的点的入度-1,
    如果入度为0,也删去,这样就只保留有用的点,
    那么从任意一个点开始,用vis数组记录是否被访问过,访问到一个新节点就累加计数器,
    然后就做出来了.bfs和dfs都可以.
    然后可以保证剩下的每个点都在一个有向环中,
    同时这个图特殊的建法好像可以保证任意两个环之间没有公共点
    3.并查集判断最小环。
    输入的每一条信息路径可以看作一条有向边,答案则是所有环中最小环的长度。
    用并查集一边合并图,一边检查新增边的两点是否已经在一个root中。
    如果为真,则增加此边后就会成环。此时环的大小为dis[x] + dis[y] + 1,
    即为所求答案的一个值。
    若为假则增加这条边。
    维护并查集时引入了一个dis[]数组,记录此节点到根节点的距离(途径边数),
    初始化都为0(自己到自己,不存在边)。
    若根节点被并入成为另一个子图的儿子,它的子节点的dis在Find的时候被更新。
    若成功新并入一条边,新边出发点的dis在Union的时候被更新。
    /*
    /*
    做法1:Tarjan算法
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <stack>
    using namespace std;
    
    const int Maxn =200005;
    struct node
    {
        int low,index;
        node(int low=-1,int index=-1):low(low),index(index){}
    }a[Maxn];
    int v[Maxn];
    int n;
    int Next[Maxn];
    int sccnum[Maxn];
    int cnt,ans=0x7ffff;
    int scc_cnt;
    stack<int> s;
    
    void Tarjan(int x)
    {
        a[x].index=a[x].low=++cnt;
        s.push(x);
        v[x]=1;
        if(v[Next[x]])
            a[x].low=min(a[x].low,a[Next[x]].index);
        else    if(!sccnum[Next[x]])
        {
            Tarjan(Next[x]);
            a[x].low=min(a[x].low,a[Next[x]].low);
        }
        if(a[x].low==a[x].index)
        {
            int l,tot=0;
            scc_cnt++;
            do
            {
                sccnum[l]=scc_cnt;
                l=s.top();
                tot++;
                s.pop();
            }
            while(l!=x);
            if(tot<=1)  return;
            else ans=min(tot,ans);
        }
    }
    
    int main()
    { 
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>Next[i];
        for(int i=1;i<=n;i++)
            if(!v[i])
                Tarjan(i);
        cout<<ans<<endl;
    }
    */  
    /*
    删掉入度为0的点直接dfs求连通块
    注意为了方便这里并没有直接删除结点而是将v[x]标记为1
    就可以区分开来
    */
    /*
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    using namespace std;
    
    const int Maxn=200010;
    int ans=0x7fffff;
    int n;
    int to[Maxn];
    bool v[Maxn];
    int in[Maxn];
    
    void topo(int x)
    {
        in[to[x]]--;//邻接点入度-1
        v[x]=1;
        if(!in[to[x]])
            topo(to[x]);
    }
    
    void dfs(int x,int tot)
    {
        v[x]=1;
        if(!v[to[x]])
            dfs(to[x],tot+1);
        else    if(tot!=1)
            ans=min(ans,tot);
    }
    
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>to[i];
            in[to[i]]++;
        }
        for(int i=1;i<=n;i++)
            if(!in[i]&&!v[i])
                topo(i);
        for(int i=1;i<=n;i++)
            if(!v[i])
                dfs(i,1);
        cout<<ans<<endl;
        return 0;
    }
    */
    /*
    并查集做法,具体见代码咯,因为是按照边合并的所以肯定不会有独立点的情况
    就可以不用特判独立点咯
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int Maxn=200005;
    int f[Maxn];
    int dis[Maxn];//初始化0
    int n;
    int ans=0x7fffff;
    
    void init()
    {
        for(int i=1;i<=n;i++)
            f[i]=i;
    }
    
    int getfather(int x)
    {
        if(x==f[x])
            return x;
        int root=f[x];
        f[x]=getfather(f[x]);//这句话要在前面不然WA(先压缩路径?)
        dis[x]+=dis[root];//更改dis路径长度
        return f[x];
    }
    
    void Union(int x,int y)
    {
        int x1=getfather(x);
        int y1=getfather(y);
        if(x1!=y1)
        {
            f[x1]=y1;//合并集合
            dis[x]=dis[y]+1;//更改长度
        }
        else//找到环了
            ans=min(ans,dis[x]+dis[y]+1);//距离为dis[x]+dis[y]+1
    }
    
    int main()
    {
        cin>>n;
        init();
        int x;
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            Union(i,x);//合并
        }
        cout<<ans<<endl;
        return 0;
    }
    
    
  • 1
    @ 2018-03-25 02:47:29

    乍看是tarjan,再一看每个点出度都是1,所以链的形状是“1”或“6”或“0”,简化成看到有旧时间戳直接返回即可。O(n)解决。

    #include <stdio.h>
    
    int next[200001], order[200001] = {0}, chain[200001] = {0}, current_chain = 0;
    
    int visit(int x, int o)
    {
        if ((chain[x] > 0) && (chain[x] != current_chain)) return 0;
        chain[x] = current_chain;
        if (order[x]) return o - order[x];
        order[x] = o;
        if (!next[x]) return 0;
        return visit(next[x], o + 1);
    }
    
    int main()
    {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &next[i]);
        int ans = n;
        for (int i = 1; i <= n; i++)
            if (!chain[i])
            {
                current_chain++;
                int temp = visit(i, 0);
                if ((temp) && (temp < ans)) ans = temp;
            }
        printf("%d", ans);
    }
    
  • 1
    @ 2017-10-27 22:14:13

    不就是个tarjan嘛......

    #include <stdio.h>
    #include <algorithm>
    #include <stack>
    using namespace std;
    const int maxn=2e5+5;
    
    int n;
    int t[maxn];
    int ans=0x7f7f7f7f;
    int dfn[maxn],low[maxn],idx;
    stack<int>sta;
    bool in[maxn];
    
    int cnt[maxn],Bcnt;
    
    void tarjan(int u){
        
        dfn[u]=low[u]=++idx;
        sta.push(u);
        in[u]=1;
        
        int v=t[u];
        if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
        else if(in[v]) low[u]=min(low[u],dfn[v]);
        
        if(low[u]==dfn[u]){
            
            Bcnt++;
            do{
                v=sta.top();
                sta.pop();
                in[v]=0;
                cnt[Bcnt]++;
            }while(u!=v);
            
        }
    }
    
    int main(){
        
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&t[i]);
        
        for(int i=1;i<=n;i++){
            if(!dfn[i]) tarjan(i);
        }
        
        for(int i=1;i<=Bcnt;i++)
            if(cnt[i]!=1) ans=min(ans,cnt[i]);
        printf("%d",ans);
        return 0;
        
    }
    
  • 1
    @ 2017-08-10 10:11:03

    稍微优化了一下, 目前应该是比较快的算法时间复杂度应该能到O(n)

    #include <cstdio>
    #include <cctype>
    
    const int MAXN = 200010, INF = 0x7fffffff;
    
    int n, p, t, x(INF), a[MAXN], f[MAXN], v[MAXN];
    
    //读入优化
    inline int ReadInt() {
      char _c; register int sum(0);
      while (!isdigit(_c = getchar()));
      do sum = sum * 10 + _c - '0';
      while (isdigit(_c = getchar()));
      return sum;
    }
    
    //输出优化
    inline void PutInt(int x) {
      char num[10]; int top(0);
      while (x) num[++top] = x % 10 + '0', x /= 10;
      do putchar(num[top]); while (--top);
      putchar('\n'); return;
    }
    
    int main() {
      n = ReadInt();
        //循环展开
      for (register int i = 1; i < n; i += 2)
        a[i] = ReadInt(), a[i + 1] = ReadInt();
      (n & 1) && (a[n] = ReadInt());
      for (register int i = 1; i <= n; ++i) {
        v[i] = 1, t = i, p = a[i];
        while (f[p] - i) {
          if (f[p] && f[p] < i) break;
          v[p] = v[t] + 1, f[t] = i, t = p, p = a[t];
        }
        (!(f[p] - i) && (x > v[t] + 1 - v[p])) && (x = v[t] + 1 - v[p]);
      } PutInt(x);
      return 0;
    }
    
  • 0
    @ 2017-11-10 19:50:44
    uses
        math;
    
    const
        inf = 200000;
    
    var
        f, d: array[1..200000] of longint; // father, distance
        n, i, j, ans: longint;
    
    function fa(x: longint): longint; // find father
    var
        temp: longint;
    begin
        if f[x]<>x then
        begin
            temp:= f[x];
            f[x]:= fa(temp);
            d[x]:= d[x] + d[temp];
        end;
        exit(f[x]);
    end;
    
    procedure un(x, y: longint); // union
    var
        p, q: longint;
    begin
        p:= fa(x); q:= fa(y);
        f[p]:= q;
        d[x]:= d[y] + 1;
    end;
    
    procedure li(x, y: longint); // link
    var
        p, q: longint;
    begin
        p:= fa(x); q:=fa(y);
        if p=q then
            ans:= min(ans, d[x] + d[y] + 1)
        else
            un(x, y);
    end;
    
    begin // main
        read(n);
        for i:= 1 to n do
        begin
            f[i]:= i;
            d[i]:= 0;
        end;
        ans:= inf;
        for i:= 1 to n do
        begin
            read(j);
            li(i, j);
        end;
        write(ans);
    end.
    
  • 0
    @ 2017-11-05 14:37:42

    双DFS求强连通分量
    var
    n,i,j,m,p:longint;
    t:array[1..200000]of boolean;
    s,q:array[1..200000]of longint;
    procedure dfs(x:longint);
    begin
    t[x]:=false;
    if t[s[x]] then dfs(s[x]);
    inc(p);
    q[p]:=x;
    end;

    begin
    readln(n);
    for i:=1 to n do
    read(s[i]);
    p:=0;
    fillchar(t,sizeof(t),255);
    for i:=1 to n do
    if t[i] then dfs(i);
    m:=200000;
    fillchar(t,sizeof(t),255);
    for i:=1 to n do
    if t[q[i]] then
    begin
    p:=1;
    j:=q[i];
    t[j]:=false;
    while t[s[j]] do
    begin
    inc(p);
    j:=s[j];
    t[j]:=false;
    end;

    if (p>1)and(p<m) then m:=p;
    end;
    write(m);
    end.

  • 0
    @ 2017-11-05 10:15:08

    70分代码
    纯粹模拟
    以样例2 4 2 3 1为例
    当2在第三轮得知自己的生日时
    第二轮的1和3必然知道2的生日
    以此逆推
    由一到n依次dfs下去
    寻找最先出现自己的轮数
    再在1到n中寻找最小的那一个值
    注意:以5为例;没人告诉过五 所以五永远不知自己的生日
    此时5的最小轮数为0
    比较时要先判断不为零。
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <vector>
    #include <queue>
    #define N 10000000+100
    using namespace std;
    int n,to[N],num[N],t,step,path,ans=N,fg;
    vector<int>q[20001];
    void dfs(int x)
    {
    if(x==fg&&step!=0){path=step;return;}
    //if(q[x].size()==0)path=N;
    for(int i=0;i<q[x].size();i++)
    {
    step++;
    dfs(q[x][i]);
    step--;
    }
    }
    int main()
    {
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    cin>>to[i];
    q[to[i]].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
    path=0;
    step=0;
    fg=i;
    dfs(i);
    num[i]=path;
    }//for(int i=1;i<=n;i++)cout<<num[i]<<endl;
    for(int i=1;i<=n;i++)
    {
    if(num[i]!=0)
    ans=min(ans,num[i]);
    }
    cout<<ans;
    return 0;
    }

  • 0
    @ 2017-11-04 11:25:13

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int ok,fa[200001],n,i,j,a[200001],c,x,k,m,used[200001],ans1=100860,ans;
    int search(int n)
    {
    if(n!=fa[n])
    return search(fa[n]);
    else
    return n;
    }
    int dfs(int n)
    {
    if(used[n]==1)
    return ans;
    if(n!=a[n]&&used[n]==0)
    {
    ans++;
    used[n]=1;
    dfs(a[n]);
    }

    }
    int main()
    {
    //freopen("message.in","r",stdin);
    //freopen("message.out","w",stdout);
    cin>>n;
    for(i=1;i<=n;i++)
    fa[i]=i;
    for(i=1;i<=n;i++)
    cin>>a[i];
    for(i=1;i<=n;i++)
    {
    int s1=search(i);
    int s2=search(a[i]);
    if(s1!=s2)
    fa[s1]=s2;
    }
    for(i=1;i<=n;i++)
    if(fa[i]==i)
    {
    ans=0;
    ans1=min(ans1,dfs(i));
    }
    cout<<ans1;
    //fclose(stdin);
    //fclose(stdout);
    return 0;
    }

  • 0
    @ 2017-10-23 16:58:56
    #include <iostream>
    #include <iomanip>
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <algorithm>
    #include <cctype>
    #include <vector>
    #include <queue>
    using namespace std;
    int a[200001],b[200001];
    int main()
    {
        int n,ans=2147483647,t=0,s,j;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++)
        {
            if(!b[i])
            {
                t++;
                s=t;
                for(j=i;!b[j];j=a[j])
                {
                    t++;
                    b[j]=t;
                }
                if(b[j]>=s)
                {
                    ans=min(ans,t-b[j]+1);
                }
            }
        }
        printf("%d",ans);
        return 0;
    }
    
  • 0
    @ 2017-10-16 15:11:55

    tarjan缩点,注意判断是否大小为1。

    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #define LL long long
    using namespace std;
    template <class _T> inline void read(_T &_x){
        int _t;bool _flag=0;
        while((_t=getchar())!='-'&&(_t<'0'||_t>'9'));
        if(_t=='-')_flag=1,_t=getchar();_x=_t-'0';
        while((_t=getchar())>='0'&&_t<='9')_x=_x*10+_t-'0';
        if(_flag)_x=-_x;
    }
    const int maxn=2e5+5;
    int n,cnt,x,top,idx,num[maxn],S[maxn],f[maxn],low[maxn],dfn[maxn],head[maxn],ans=0x3f3f3f3f;
    bool ins[maxn];
    struct edge{
        int v,nxt;
    }d[maxn];
    inline void add(int a,int b){
        d[++cnt].v=b;d[cnt].nxt=head[a];head[a]=cnt;
    }
    int find(int x){
        return x==f[x]? x:f[x]=find(f[x]);
    }
    void tj(int u){
        int v;
        dfn[u]=low[u]=++idx;
        S[++top]=u;ins[u]=1;
        for(int i=head[u];i;i=d[i].nxt){
            v=d[i].v;
            if(!dfn[v]){
                tj(v);
                low[u]=min(low[v],low[u]);
            }
            else if(ins[v])low[u]=min(dfn[v],low[u]);
        }
        if(dfn[u]==low[u]){
            while(u!=v){
                v=S[top--];
                ins[v]=0;
                int f1=find(u),f2=find(v);
                f[f2]=f1;
                if(f1!=f2)num[f1]+=num[f2];
            }
        }
    }
    int main(){
        read(n);
        for(int i=1;i<=n;i++){
            read(x);
            add(i,x);
        }
        for(int i=1;i<=n;i++)f[i]=i,num[i]=1;
        for(int i=1;i<=n;i++)if(!dfn[i])tj(i);
        for(int i=1;i<=n;i++){
            int tmp=num[find(i)];
            if(tmp!=1)ans=min(ans,tmp);
        }
        printf("%d",ans);
        return 0;
    }
    
  • 0
    @ 2017-09-16 16:29:35

    我是wys,
    发一波题解(tarjan)

    #include<cstdio>
    #include<stack>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=200005;
    const int INF=0x3f3f3f3f;
    int n;
    int cnt=0,num=0;
    int a[maxn];
    int dfn[maxn],low[maxn],belong[maxn];
    int sq[maxn];//每个强连通分量所含边数  强连通分量中 边数==点数; 
    bool instack[maxn];
    stack<int > S;
    void tarjan(int u){//tarjan
        dfn[u]=low[u]=++cnt;
        S.push(u);
        instack[u]=true;
        int v=a[u];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(instack[v])
            low[u]=min(low[u],dfn[v]);
        if(dfn[u]==low[u]){
            num++;
            do{
                v=S.top();
                S.pop();
                belong[v]=num;
                sq[num]++;//处理边数 
            }while(dfn[v]!=low[v]);
        }
        return ;
    }
    int main(){
        int ans=INF;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=1;i<=n;i++){//由于图可分为几个强连通分量,所以不做冗余操作; 
            if(!dfn[i])
                tarjan(i);//tarjan处理强连通分量; 
        }
        for(int i=1;i<=num;i++){//找最小环边数; 
            if(sq[i]!=1)ans=min(ans,sq[i]);
        }
        printf("%d\n",ans);
    }
    
  • 0
    @ 2017-08-20 09:00:02

    //一言不合上tarjan

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

    inline ll read()
    {
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
    }

    vector<int>e[200010];
    int ind=0,scc=0;
    int num[200010],low[200010],dfn[200010],belong[200010];
    bool exist[200010],vis[200010];
    stack<int>sta;
    int ans=1000000007;
    int n;

    void tarjan(int x)
    {
    vis[x]=exist[x]=true;
    low[x]=dfn[x]=++ind;
    sta.push(x);
    for(int i=0;i<e[x].size();i++)
    {
    int p=e[x][i];
    if(!vis[p])
    {
    tarjan(p);
    low[x]=min(low[x],low[p]);
    }
    else
    {
    if(exist[p])low[x]=min(low[x],dfn[p]);
    }
    }
    int now;
    if(low[x]==dfn[x])
    {
    scc++;
    while(now!=x)
    {
    now=sta.top();
    sta.pop();
    exist[now]=false;
    belong[now]=scc;
    num[scc]++;
    }
    }
    }

    int main()
    {
    n=read();
    for(int i=1;i<=n;i++)
    {
    int u=read();
    e[i].push_back(u);
    }
    for(int i=1;i<=n;i++)
    if(!vis[i])tarjan(i);
    for(int i=1;i<=scc;i++)
    if(num[i]>1)
    ans=min(num[i],ans);
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2017-07-22 20:27:13

    拓扑排序把不在环里的点去掉,然后对在环里的点dfs(dfs时打标记避免重复dfs已经搜过的环内的点,否则会TLE的)

    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    
    
    using namespace std;
    
    const int MAXN = 200005;
    int n, t, ind[MAXN], ans = 0x7fffffff, q[MAXN<<1], hd, tl;
    bool circle[MAXN];
    
    struct Edge{
        int nxt, to;
    }edge[MAXN];
    
    int head[MAXN], edge_num;
    void add_edge(int from, int to){
        edge[++edge_num].nxt = head[from];
        edge[edge_num].to = to;
        head[from] = edge_num;
        ind[to]++;
    }
    
    void toposort(){
        for(int i = 1; i <= n; i++)
            if(ind[i] == 0)
                q[tl++] = i;
        while(hd <= tl){
            int cur = q[hd];
            for(int i = head[cur]; i; i = edge[i].nxt){
                ind[edge[i].to]--;
                if(ind[edge[i].to] == 0)
                    q[tl++] = edge[i].to;
            }
            hd++;
        }
    }
    
    void dfs(int x, int source, int res){
        circle[x] = 1;
        if(x == source && res != 0){
            ans = min(ans, res);
            return;
        }
        for(int i = head[x]; i; i = edge[i].nxt)
            dfs(edge[i].to, source, res+1);
    }
    
    int main(){
        scanf("%d", &n);
        for(int i = 1; i <= n; i++){
            scanf("%d", &t);
            add_edge(i, t);
        }
        toposort();
        for(int i = 0; i < tl; i++)
            circle[q[i]] = 1;
        for(int i = 1; i <= n; i++){
            if(!circle[i]){
                dfs(i, i, 0);
            }
        }
        printf("%d", ans);
        return 0;
    }
    
  • 0
    @ 2017-05-06 22:45:21

    include <cstdio>

    using namespace std;

    define N 200010

    int main()
    {
    int n=0,m=0; //人数,多少轮
    int a[N]={0},birthday[N][N]={0},hi[N][N]={0};
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
    scanf("%d",&a[i]);
    hi[i][1]=i;
    }

    // -----------------------------------------

    for(int b=1;b<=n;b++)
    {
    m++;
    for(int i=1;i<=n;i++)
    {
    int p=a[i];
    for(int j=1;j<=n;j++)
    {

    birthday[p][j]=hi[i][j];
    if(hi[i][j]==p)
    {
    printf("%d",m);
    return 0;
    }
    if(hi[i][j]==0)
    {
    break;
    }
    }
    }
    for(int i=1;i<=n;i++)
    {
    for(int j=1;j<=n;j++)
    {
    hi[i][j]=0;
    }
    }
    for(int i=1;i<=n;i++)
    {
    for(int j=1;j<=n;j++)
    {
    hi[i][j]=birthday[i][j];
    if(birthday[i][j]==0)
    {
    break;
    }
    }
    }

    }
    return 0;
    }

  • 0
    @ 2017-02-06 19:07:44
    就我一个人用了Tarjan吗?
    
    #include<iostream>
    #include<cstring>
    #include<stack>
    using namespace std;
    int n;
    int a[200001],dfn[200001],low[200001],index=0,ltfl=0,p[200001],minn=2000000;
    bool instack[200001];
    stack<int> s;
    void tarjan(int i){
        dfn[i]=low[i]=++index;
        instack[i]=true;
        s.push(i);
        int j=a[i];
        if(!dfn[j]){
            tarjan(j);
            if(low[i]>low[j])low[i]=low[j];
        }else
        if(instack[j]&&low[i]>dfn[j])low[i]=dfn[j];
        if(low[i]==dfn[i]){
            ltfl++;
            int t=0;
            do{
                t++;
                j=s.top();
                s.pop();
                p[j]=ltfl;
            }while(j!=i);
            if(t>1&&t<minn)minn=t;
        }
    }
    int main(){
        ios::sync_with_stdio(false);
        cin>>n;
        for(int i=1;i<=n;i++)
        cin>>a[i];
        memset(instack,0,sizeof(instack));
        memset(dfn,0,sizeof dfn);
        memset(low,0,sizeof low);
        for(int i=1;i<=n;i++)
        if(!dfn[i]){
            tarjan(i);
        }
        cout<<minn<<endl;
        return 0;
    }
    
    • @ 2017-02-07 09:57:05

      自己的代码似乎有个bug

信息

ID
1979
难度
6
分类
(无)
标签
递交数
4096
已通过
980
通过率
24%
被复制
9
上传者