UVA10305

#include<stdio.h>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 110;
int vis[N];
int ans[N];
int G[N][N];
int n,m,t;
bool  dfs(int u)
{
    vis[u] = -1;
    for(int v=1;v<=n;++v)
        if(G[u][v])
        {
            if(vis[v]<0) return false;  //如果v正在被访问（说明有环）
            else if(!vis[v]&&!dfs(v)) return false;  //v没被访问过就去访问v
        }
    vis[u]=1;
    ans[--t]=u;
    //cout<<ans[t+1]<<endl;
    return true;

}
bool topo_sort()
{
    t=n;
    memset(vis,0,sizeof(vis));
    for(int u=1;u<=n;++u)
    {
        if(!vis[u])
            if(!dfs(u)) return false;
    }
    return true;
}
int main()
{

    while(scanf("%d%d",&n,&m)==2&&n)
    {
        memset(G,0,sizeof(G));
        while(m--)
        {
            int i,j;
            scanf("%d%d",&i,&j);
            G[i][j]=1;
        }
        if(topo_sort())
        {
            for(int i=0;i<n;++i)
            {
                if(i==0) printf("%d",ans[i]);
                else printf(" %d",ans[i]);
            }
            printf("\n");

        }


    }
    return 0;
}

题目链接：http://hihocoder.com/contest/icpcbeijing2018/problem/1

思路：拓扑排序判环

map<string,int>把string换成数字方便建图

map<int,string>方便输出人名

#include<iostream>
#include<map>
#include<cstring>
using namespace std;
map<string,int> mp;
map<int,string> mm;
int n;
int cnt;
int G[50][50];
int vis[50];
bool dfs(int u)
{
    vis[u]=-1;
    for(int v=1;v<=cnt;++v)
    {
        if(G[u][v]==1)
        {
            if(vis[v]==-1)
            {
                cout<<mm[u]<<" "<<mm[v]<<endl;
                return false;
            }
            else if(!vis[v]&&!dfs(v)) return false;
        }
    }
    vis[u]=1;
    return true;

}
bool topo_sort()
{
    memset(vis,0,sizeof(vis));
    for(int u=1;u<=cnt;++u)
    {
        if(!vis[u])
        {
            if(!dfs(u))
                return false;
        }
    }
    return true;

}
int main()
{
    while(cin>>n)
    {
        cnt=0;
        memset(G,-1,sizeof(G));
        mp.clear();
        mm.clear();
        while(n--)
        {
            string a,b;
            cin>>a>>b;
            if(mp[a]==0) mp[a]=++cnt,mm[cnt]=a;
            if(mp[b]==0) mp[b]=++cnt,mm[cnt]=b;
            G[mp[a]][mp[b]]=1;
        }
        if(topo_sort()) cout<<0<<endl;
    }
    return 0;
}