7-9 谁是真正的首富（25 分)

以你之姓@ 2022-03-08 11:16 142阅读 0赞

### 题目描述： ###

有n个富豪，他们聚在一起想要知道谁才是他们之中的最有钱的人，然而他们所有人都隐藏了家产，根据调查，你知道了m个富豪之间的的财富关系。现在你要根据已有的关系信息推理出这n个人之中谁才是真正的首富。

输入格式:  
多组输入。每组第一行输入2个整数n,m（0<=m，n<=1000000）,当n=m=0时结束输入。接下来m行，每行输入一个整数a(1<=a<=n)，一个字符c，和一个整数b(1<=b<=n)，表示编号为a的富豪与编号为b（a不等于b）的富豪的财富关系，关系只有两种：大于或是小于。保证输入关系无矛盾，如1>2，2>3，3>1这种情况是矛盾的。

输出

输出格式:  
若能推理出谁是首富，则输出首富的编号，否则输出“no solution”（不含双引号）。

样例输入

输入样例:  
在这里给出一组输入。例如：

3 2  
1 > 3  
2 > 3  
3 2  
1 > 2  
2 > 3  
输出样例:  
在这里给出相应的输出。例如：

no solution  
1

##### 分析： #####

这个题呀，在打比赛的时候，真的是一脸懵。  
后来， 学长说是拓扑排序。 顿时就懂了。  
然后， 在看学长代码发现压根就可以不用拓扑排序。  
直接判断是不是只有一个点的入度为0就好了。  
AC代码：

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    int dp[1000001]= {0};
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            if(n==0&&m==0)
                break;
            memset(dp,0,sizeof(dp));
            for(int i=0; i<m; i++)
            {
                int a,b;
                char c;
                scanf("%d %c %d",&a,&c,&b);
                if(c=='>')
                    dp[b]++;
                else
                    dp[a]++;
            }
            int cnt=0;
            int mark=0;
            for(int i=1; i<=n; i++)
            {
                if(dp[i]==0)
                {
                    cnt++;
                    if(mark==0)
                        mark=i;
                }
            }
            if(cnt==1)
                printf("%d\n",mark);
            else
                printf("no solution\n");
        }
    }