【拓扑排序】MicroRNA Ranking

题目描述

Ahlaam is a computer science student, doing her master thesis on a bioinformatics project about MicroRNAs, special molecule types found in cells. During her thesis, she wants to find microRNAs relevant to a specific health factor in human beings.
Ahlaam has designed k microRNA ranking algorithms, each of which ranks microRNAs from a specific point of view.
There are n microRNAs numbered 1 through n, and each algorithm produces one permutation of these n microRNAs. In the permutation produced by each algorithm, the first microRNA is inferred by the algorithm as the most relevant one to the health factor, and the last microRNA is inferred as the least relevant one. 
Ahlaam wants to report a consensus ranking on microRNAs. In a consensus ranking, if microRNA i is ranked before another mircroRNA j, then at least half of the algorithms should have ranked i before j. Write a program to help Ahlaam find a consensus ranking.

 

输入

There are multiple test cases in the input. The first line of each test contains two space-separated integers n (1 ⩽ n ⩽ 1000) and k (1 ⩽ k ⩽ 200), the number of microRNAs and the number of ranking algorithms, respectively. Then, there are k lines, where the i-th line contains a permutation of n numbers 1, . . . , n, representing the output of the i-th ranking algorithm. The input terminates with a line containing 0 0 which should not be processed.

 

输出

For each test case, print a single line containing a permutation of n numbers 1, . . . , n, representing a possible consensus ranking. If there are more than one correct consensus rankings, print the first one in lexicographic order (a sequence a1 , . . . , an is lexicographically less than a sequence b1 , . . . , bn iff there exists a positive integer j such that ai = bi for all 1 ⩽ i ⩽ j   1 and aj < bj ) . If no such a ranking exists, write “No solution” instead.

 

样例输入

5 3
3 2 4 1 5
4 1 5 2 3
2 4 5 1 3
5 2
5 4 3 2 1
1 2 3 4 5
4 3
1 4 2 3
4 2 3 1
3 1 2 4
0 0

 

样例输出

2 4 1 5 3
1 2 3 4 5
No solution

思路：

　　首先，求出各个数的相对位置，然后将相对位置如dp[i][j]，理解为i是j的前置，显然就是拓扑排序，但是我训练的数组开小了，不明白啊，我明明特意开大了呀，又坑队友了

代码如下：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+50;
vector<int> vec[maxn];
int n,k,num=0;
int indeg[maxn];
int dp[250][1050];
int a[1050];
int b[1050];
priority_queue<int,vector<int>,greater<int> > q;
void init()
{
    memset(dp,0,sizeof(dp));
    memset(indeg,0,sizeof(indeg));
    for(int i=1;i<=n;i++)
    {
        vec[i].clear();
    }
}
void build()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(dp[i][j]>dp[j][i])
            {
                vec[i].push_back(j);
                indeg[j]++;
            }
            if(dp[j][i]>dp[i][j])
            {
                vec[j].push_back(i);
                indeg[i]++;
            }
        }
    }
}
bool topsort()
{
    while(!q.empty())
        q.pop();
    num=0;
    for(int i=1;i<=n;i++){
        if(!indeg[i]){
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int now=q.top();
        q.pop();
        b[num]=now;
        num++;
        for(int i=0;i<vec[now].size();i++)
        {
            indeg[vec[now][i]]--;
            if(indeg[vec[now][i]]==0)
                q.push(vec[now][i]);
        }
    }
    if(num==n)
        return true;
    else
        return false;
}
void judge()
{
    if(topsort())
    {
        for(int i=0;i<n;i++)
        {
            if(i)
                printf(" ");
            printf("%d",b[i]);
        }
        printf("\n");
    }
    else
    {
        printf("No solution\n");
    }
}
int main()
{
    while(scanf("%d %d",&n,&k)!=EOF&&n&&k)
    {
        init();
        for(int i=1;i<=k;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&a[j]);
            }
            for(int j=1;j<=n;j++)
            {
                for(int q=j+1;q<=n;q++)
                {
                    dp[a[j]][a[q]]++;
                }
            }
        }
        build();
        judge();
    }
    return 0;
}