BZOJ1607: [Usaco2008 Dec]Patting Heads 轻拍牛头
BZOJ4123: [Baltic2015]Hacker

BZOJ1773: [Usaco2009 Dec]Dizzy 头晕的奶牛

shinbokuow posted @ Aug 19, 2015 10:07:27 AM in BZOJ with tags 图论 构造 图连通性 , 1390 阅读

题解:

这道题没有SPJ...

但是http://oj.jdfz.com.cn:8081/oldoj/problem.php?id=1013这里是可以正常提交的...

考虑一开始给出的若干有向边,若存在环一定是无解的.

否则,我们利用现在的DAG随意得到一个拓扑序列.

给剩下的边定向时,我们总是让在序列前面的点指向序列后面的点.

这样一定是满足要求的.

代码:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 100010
#define M 100010
int head[N],next[M],end[M],in[N];
inline void addedge(int a,int b){
    static int q=1;
    end[q]=b;
    next[q]=head[a];
    head[a]=q++;
    ++in[b];
}
 
int q[N],fr,ta,ins[N];
int main(){
    int n,m1,m2;
    cin>>n>>m1>>m2;
    int a,b,i,j;
    for(i=1;i<=m1;++i){
        scanf("%d%d",&a,&b);
        addedge(a,b);
    }
    for(i=1;i<=n;++i)
        if(!in[i])
            q[ta++]=i;
    while(fr!=ta){
        i=q[fr++];
        for(j=head[i];j;j=next[j])
            if(!--in[end[j]])
                q[ta++]=end[j];
    }
    if(ta!=n)
        cout<<-1<<endl;
    else{
        for(i=0;i<ta;++i)
            ins[q[i]]=i;
        for(i=1;i<=m2;++i){
            scanf("%d%d",&a,&b);
            if(ins[a]>ins[b])
                swap(a,b);
            printf("%d %d\n",a,b);
        }
    }
    return 0;
}
charlly 说:
Oct 11, 2022 10:21:46 AM

Writing quick and effective programmes was the main objective of computer programmers for a very long time. The "level of the programming language" is the first factor programmers take into account when selecting a language to write in. engagement rings This is a useful page to find this kind of code information.

rowli 说:
Nov 01, 2022 02:19:31 PM

This is the website that helps you to understand and study about various programming language. Can also download this website and also subscribe the platform positive effects of CBD usage for understanding more about the programming language and how to handle this in a platform


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter