CF915D Almost Acyclic Graph

题目链接：http://codeforces.com/contest/915/problem/D

题目大意：

　　给出一个\(n\)个结点\(m\)条边的有向图(无自环、无重边，2 ≤ n ≤ 500, 1 ≤ m ≤ min(n(n - 1), 100000) )，问能否通过删除其中的某一条边，使得该图无环。

知识点：　　拓扑排序、DFS

解题思路一：

　　由于结点数不多，所以可以枚举每个入度不为\(0\)的点，删去通向它的一条边（即使其入度减一），再跑拓扑排序判断有没有环。

AC代码一：

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = , maxm = ;

 vector<int> G[maxn];

 int in[maxn],tin[maxn],stac[maxn];

 bool topo(int n){

     int top=,ending=;

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

         if(tin[i]==)

             stac[ending++]=i;

     }

     while(top<ending){

         int now=stac[top];

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

             tin[G[now][i]]--;

             if(tin[G[now][i]]==)  stac[ending++]=G[now][i];

         }

         top++;

     }

     return ending>=n;

 }

 int main(){

     int n,m;

     scanf("%d%d",&n,&m);

     for(int i=;i<m;i++){

         int u,v;

         scanf("%d%d",&u,&v);

         in[v]++;

         G[u].push_back(v);

     }

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

         if(in[i]!=){

             for(int j=;j<=n;j++)   tin[j]=in[j];

             tin[i]--;

             if(topo(n)) return *puts("YES");

         }

     }

     return *puts("NO");

 }

解题思路二：

　　先找出一个简单环，然后枚举删除该环上的每一条边，再跑拓扑排序判断还有没有环。

AC代码二：

#include <bits/stdc++.h>

using namespace std;

const int maxn = ;

vector<int> G[maxn];

int mark[maxn],in[maxn],tin[maxn],last[maxn];

int cnt, loop[maxn];//cnt记录环上的结点数

bool dfs(int rt,int la){

    last[rt]=la;

    mark[rt]=;     //访问过的结点,mark=1;

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

        if(mark[G[rt][i]]==){ //没有访问过的结点, mark=0

            if(dfs(G[rt][i],rt))    return true;

        }

        if(mark[G[rt][i]]==){

            int now=rt;

            cnt=;

            while(now!=G[rt][i]&&now!=-){

                loop[cnt++]=now;

                now=last[now];

            }

            loop[cnt++]=G[rt][i];

            return true;

        }

    }

    mark[rt]=-;   //访问过并且会走到死路的结点，mark=-1

    return false;

}

int stac[maxn];

bool topo(int n,int from,int to){//拓扑排序检查是否有环

    int top=,ending=;

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

        if(tin[i]==)

            stac[ending++]=i;

    }

    while(top<ending){

        int now=stac[top];

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

            if(now==from&&G[now][i]==to)    continue;

            tin[G[now][i]]--;

            if(tin[G[now][i]]==)  stac[ending++]=G[now][i];

        }

        top++;

    }

    return ending>=n;

}

int main(){

    int n,m;

    scanf("%d%d",&n,&m);

    for(int i=;i<m;i++){

        int u,v;

        scanf("%d%d",&u,&v);

        G[u].push_back(v);

        in[v]++;    //记录入度

    }

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

        if(mark[i]==){

            if(dfs(i,-))  break;

        }

    }

    if(!cnt)    return *puts("YES");

    for(int i=;i<cnt;i++){

        for(int j=;j<=n;j++)   tin[j]=in[j];

        tin[loop[(i+)%cnt]]--;

        if(topo(n,loop[i],loop[(i+)%cnt])) return *puts("YES");

    }

    return *puts("NO");

}

巴特西

CF915D Almost Acyclic Graph

最新文章

热门文章