Tag:Topological sort
Article From:https://www.cnblogs.com/cangT-Tlan/p/9063510.html

Mixed graph (dizzy.pas/cpp/c)

【Title Description]

  HzwerShen Juan recently conquered a country, and then came across a difficult problem.

  HzwerThe country has n points and m edges, and as a king, he likes to visit his country very much. He usually starts at any point, looks for it and walks, enjoying the beautiful scenery along the way. But our Hzwer is a strange person. He doesn’t like to go where he used to go.P1 has a direction to the side, P2 undirected edge. Because of the king’s strange hobby, he feels that he reorganizes all the undirected edges to make them turn to the side. (Note: m=p1+p2.)

  Overview: give you a mixed graph that requires you to orientate the undirected graph so that there is no ring on the graph.

【Input format] dizzy.in

      The first row, 3 integers n, P1, P2, respectively denote the number of points, the number of directed edges, the number of undirected edges.

      In the second row, input P1 rows, each row has 2 integers a, B means a to B has a directed edge.

      Next, enter the P2 row, each row has 2 integers a, B means a and B have an undirected edge in the middle.

【Output format] dizzy.out

  For each undirected edge, we need to output the result of your orientation in the order of input, that is, if you output a B, that means you orientate the undirected edge between a and B to a-> b.

  Note that there may be a lot of feasible solutions. You just have to output any of them.

【Sample input]

4 2 3

1 2

4 3

1 3

4 2

3 2

【Sample output]

1 3

4 2

2 3

 

Data range

For 20% data n< =10 p1< =10 p2< =5

For 30% data n< =10 p1< =30 p2< =20

For 100% data n< =100000 p1< =100000 p2< =100000

The data guarantee has at least one feasible solution.

Ideas:If you look at a directed edge, the original graph is a directed acyclic graph, that is, a topological graph. If the end is still a topological graph, then it is still acyclic.

For the original map to do topological sorting, get the time of each point, the edge of the edge to the point from the early point of the team to the late point, the original order of entry is still set up, no ring.

Complexity O (p1+p2)

Do not know the code that is not right (because the verifier has gone wrong ~ ~ ~ (> _<) ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ – ~, put the data and the verifier, have the test of the test, put it in the file).

 

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 100010
using namespace std;
queue<int>que;
int n,p1,p2,tot,num;
int into[MAXN],vis[MAXN];
int to[MAXN],net[MAXN],head[MAXN];
void add(int u,int v){ to[++tot]=v;net[tot]=head[u];head[u]=tot; }
int main(){
    //freopen("dizzy.in","r",stdin);
    //freopen("dizzy.out","w",stdout);
    scanf("%d%d%d",&n,&p1,&p2);
    for(int i=1;i<=p1;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);into[b]++;
    }
    for(int i=1;i<=n;i++)
        if(!into[i]){ vis[i]=++num;que.push(i); }
    while(!que.empty()){
        int now=que.front();
        que.pop();
        for(int i=head[now];i;i=net[i]){
            into[to[i]]--;
            if(!into[to[i]]){
                vis[to[i]]=++num;
                que.push(to[i]);
            }
        }
    }
    for(int i=1;i<=n;i++)    cout<<vis[i]<<" ";cout<<endl;
    for(int i=1;i<=p2;i++){
        int a,b;scanf("%d%d",&a,&b);
        if(vis[a]<vis[b])    printf("%d %d\n",a,b);
        else if(vis[a]>vis[b])    printf("%d %d\n",b,a);
    }
    return 0;
}
/*
4 2 3
1 2
4 3
1 3
4 2
3 2
*/

 

 

 

 
Link of this Article: Mixed graph (dizzy.pas/cpp/c)

Leave a Reply

Your email address will not be published. Required fields are marked *