1459.排位
Time Limit: 2000 MS Memory Limit: 65536 K
Total Submissions: 248 (75 users) Accepted: 54 (50 users)
[ My Solution ]
Description
在競技比賽中, 為了衡量一支隊伍在比賽中的能力水平, 我們常常需要使用到排位順序的概念, 其中, 排位越靠前的隊伍, 能力越強。現在, 已知n支隊伍參加了某項比賽和其中一些隊伍排位的先後次序關系, 你能確定出這些隊伍的排名情況嗎？
Input
輸入的第一行有2個整數n, m (2 <= n <= 100,000, 0 <= m <= 200,000), 接下來有m行, 每行兩個正整數x, y (1 <= x, y <= n, 且 x != y)代表編號為x的隊伍的排位在編號為y的隊伍之前。
Output
如果任何一種排位順序都不滿足要求, 則輸出-1, 否則, 請按排位的先後順序輸出n支隊伍的編號, 每兩個數字之間保留一個空格, 若存在多種滿足題意的排位順序, 則輸出任意一種都可以通過本題。
Sample Input
4 3
3 4
2 1
1 3
Sample Output
2 1 3 4
Hint
這是一道SPECIAL JUDGE的題目, C++建議使用scanf讀入, printf輸出
Source
doraemon @ xmu
題意：
輸入 n m
n個人 m個關系
對於每個關系a b 表示a在b的前面
問輸入這些之後 所有點的最後的前後順序應該是什麼 可以有多種答案 special judge
思路：
模板題 ：拓撲排序
[cpp]
#include<stdio.h>
#include<malloc.h>
#include<queue>
using namespace std;
int m,n;
const int mmax=100100;
struct haha
{
int son;
struct haha *nextson;
}*e[mmax];
int in[mmax],ans[mmax];
void add_edge(int x,int y)
{
struct haha *p;
p=(struct haha *)malloc(sizeof(struct haha));
p->son=y;
p->nextson=e[x];
e[x]=p;
}
int main()
{
int i,x,y,num,cnt;
while(scanf("%d %d",&n,&m)!=EOF)
{
num=n;cnt=0;
for(i=1;i<=n;i++)
{
e[i]=NULL;
in[i]=0;
}
for(i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
add_edge(x,y);
in[y]++;
}
priority_queue<int,vector<int>,greater<int> >duilie;//注意這裡要把》 》 分開 寫
for(i=1;i<=n;i++)
if(in[i]==0) duilie.push(i);
while(!duilie.empty())
{
x=duilie.top();
duilie.pop();
ans[cnt++]=x;
struct haha *p;
p=e[x];
while(p!=NULL)
{
if(--in[p->son]==0) duilie.push(p->son);
p=p->nextson;
}
}
if(cnt!=n) {printf("-1\n");continue;}
for(i=0;i<cnt-1;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[cnt-1]);
}
return 0;
}
#include<stdio.h>
#include<malloc.h>
#include<queue>
using namespace std;
int m,n;
const int mmax=100100;
struct haha
{
int son;
struct haha *nextson;
}*e[mmax];
int in[mmax],ans[mmax];
void add_edge(int x,int y)
{
struct haha *p;
p=(struct haha *)malloc(sizeof(struct haha));
p->son=y;
p->nextson=e[x];
e[x]=p;
}
int main()
{
int i,x,y,num,cnt;
while(scanf("%d %d",&n,&m)!=EOF)
{
num=n;cnt=0;
for(i=1;i<=n;i++)
{
e[i]=NULL;
in[i]=0;
}
for(i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
add_edge(x,y);
in[y]++;
}
priority_queue<int,vector<int>,greater<int> >duilie;//注意這裡要把》 》 分開 寫
for(i=1;i<=n;i++)
if(in[i]==0) duilie.push(i);
while(!duilie.empty())
{
x=duilie.top();
duilie.pop();
ans[cnt++]=x;
struct haha *p;
p=e[x];
while(p!=NULL)
{
if(--in[p->son]==0) duilie.push(p->son);
p=p->nextson;
}
}
if(cnt!=n) {printf("-1\n");continue;}
for(i=0;i<cnt-1;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[cnt-1]);
}
return 0;
}
