学步园

http://www.codeforces.com/problemset/problem/117/C

昨天多校联合的题，有人发现在cf上也有，于是立刻去水水。

此题可以一遍拓扑排序判环求解 即只需要找到一个环，就必定存在三元环 证明如下： 假设存在一个n元环，因为a->b有边，b->a必定没边，反之也成立 所以假设有环上三个相邻的点a-> b-> c,那么如果c->a间有边，就已经形成了一个三元环，如果c->a没边，那么a->c肯定有边，这样就形成了一个n-1元环。。。。
所以只需证明n为4时一定有三元环即可，显然成立

ps:好像是个结论。。。竞赛图中只要有环，就肯定存在三元环

这题要输出路径，但是对拓扑排序毫无压力

#include<cstdio>  
#include<cstring>  
#include<queue>  
#include<vector>  
#include<algorithm>  
using namespace std;  
void Max(double &a,double b){if(b>a) a=b;}  
const int inf = ~0u>>2;  
const int maxn = 5010;
char mp[maxn][maxn];  
int n,m;  
vector<int> edge[maxn];  
int c[maxn];  
int topo[maxn];  
int T;
int ans;
int pre[maxn];
bool dfs(int u){  
    c[u]=-1;  
    for(int i=0;i<edge[u].size();i++){  
        int v=edge[u][i];  
		pre[v]=u;
		if(c[v]<0) {ans=v;return false;  }
        else if(!c[v] && !dfs(v)) return false;  
    }  
    c[u]=1;  
    topo[--T]=u;  
    return true;  
}  
bool topsort(int n){  
    T=n+1;  
    memset(c,0,sizeof(c));  
	for(int i=1;i<=n;i++) if(!c[i]){
		bool f=dfs(i);  
		if(!f) return false;
	}
	return true;
}  
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++) edge[i].clear();
        for(int i=1;i<=n;i++)
        {
            scanf("%s",mp[i]+1);
            for(int j=1;j<=n;j++)
            {
                if(mp[i][j]=='1')
                {
                    edge[i].push_back(j);
                }
            }
        }
        if(!topsort(n)) {
           printf("%d %d %d\n",pre[pre[ans]],pre[ans],ans);
        }
        else printf("-1\n");
    }
    return 0; 
}