日照做网站公司什么是互联网推广

 

 

 

 

 

 

 

大意：给出一个有向图，问能否在只去掉一条边的情况下破掉所有的环

 

 

解析：最直接的是枚举每个边，将其禁用，然后在图中找环，如果可以就YES，都不行就NO

复杂度O(N*M)看起来不超时

但是实现了以后发现即使优化到不清空vis数组（时间戳标记），也仍然超时。

因为O(N*M)已经很接近时间复杂度上界，常数稍大就GG。

不过可以脑补一下取巧算法：在不超时的前提下，随机取K个边进行检验~~~。不过数据多了就非常容易GG。理论上还是可行的。

 

 

正解：从枚举边变为枚举点，删掉到达一个点的某条边可以认为是该点入度 -1 ，然后做拓扑排序。

如果所有点都能访问到，说明没有环，YES。

如果有的点不能访问到，则说明图中存在环，删到达该点的某条边不可行。

 

入度 -1 的正确性：

可以认为是暂时不具体考虑删掉的是那条边，到了这个点的入边只剩一个没有访问的时候，该点的入度为0，可以开始以该点为起点dfs（bfs也行），如果该点正好在某个环内，就直接破掉（遍历）了这个环。、

 

/*
Welcome Hacking
Wish You High Rating
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
int read(){
    int xx=0,ff=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}
    return xx*ff;
}
const int maxn=510,maxm=100010;
int N,M,lin[maxn],len,in_[maxn],deg[maxn];
struct edge{
    int y,next;
}e[maxm];
inline void insert(int xx,int yy){
    e[++len].next=lin[xx];
    lin[xx]=len;
    e[len].y=yy;
    in_[yy]++;
}
bool vis[maxn];
void dfs(int x){
    vis[x]=1;
    for(int i=lin[x];i;i=e[i].next){
        deg[e[i].y]--;
        if(!vis[e[i].y]){
            if(deg[e[i].y]<=0)
                dfs(e[i].y);
        }
    }
}
int main(){
    //freopen("in.txt","r",stdin);
    N=read(),M=read();
    for(int i=1;i<=M;i++){
        int t1=read(),t2=read();
        insert(t1,t2);
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)
            deg[j]=in_[j];
        memset(vis,0,sizeof(vis));
        deg[i]--;
        for(int j=1;j<=N;j++)
            if((!vis[j])&&deg[j]<=0)
                dfs(j);
        bool OK=1;
        for(int j=1;j<=N;j++)
            if(!vis[j]){
                OK=0;
                break;
            }
        if(OK){
            printf("YES\n");
            return 0;
        }
    }
    printf("NO\n");
    return 0;
}