[洛谷 P2661]信息传递

danihao123 posted @ 2016年8月02日 13:38 in 题解 with tags 洛谷 NOIP 图论 DFS , 158 阅读
转载请注明出处:http://danihao123.is-programmer.com/

bi了doge了……图论基本不会了……

这提可以直接循环删除所有入度为0的边,这样就只剩环了。然后DFS嘿嘿嘿。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=200001;
int G[maxn];
int to[maxn];
bool vis[maxn];
int n;
inline bool jianz(){
    register int i;
    bool ans=false;
    for(i=1;i<=n;i++){
        if(!vis[i] && !to[i]){
            ans=true;
            to[G[i]]--;
            vis[i]=true;
            G[i]=0;
        }
    }
    return ans;
}
int dfs(int x,int y){
    if(x==y && vis[x]){
        return 0;
    }else{
        vis[x]=true;
        return dfs(G[x],y)+1;
    }
}
int getchen(){
    register int i,ans=0x5ffffff;
    while(jianz());
    for(i=1;i<=n;i++)
        if(!vis[i])
            ans=min(ans,dfs(i,i));
    return ans;
}
int main(){
    register int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&G[i]);
        to[G[i]]++;
    }
    printf("%d\n",getchen());
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter