Strongly connected components of directed graphs, exercise 1 hdu 3072 + hdu 4635 + poj 1236

4-26 -> 4-27
//
Look at the first question first:
hdu3072 : http://acm.hdu.edu.cn/showproblem.php?pid=3072
The question is meant to go round and round, sending information from the point 0 to each point , means that 0 can reach every other point, and each edge has a certain cost, but all edges in the strongly connected component have no cost. Find the minimum cost to complete this connected project

2016-5-10 Review:
T1: In fact, just keep in mind that one of the most important points of strongly connected components is the outgoing and incoming edges of each component

: At first, I was confused, and I didn’t read the meaning of the question clearly. The point is that the point 0 must be able to reach all other points. First, we can run tarjan once to get all the strongly connected components in the graph. No matter how much the cost becomes 0, and then consider this strongly connected component as a point, we need to get the minimum weight sum. It’s actually very simple, but I don’t have that thinking yet. Remember one thing: for this strongly connected component, its incoming edge and outgoing edge are very important: For example, for this question, we only need to find each strongly connected component. The smallest incoming edge of the component (the starting point is another component), and then except for the strongly connected component at 0, we add up every other strongly connected smallest incoming edge:

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
using namespace std;
#define   M 50005            //Maximum possible number of points in the title
 int STACK[M],top;           //stack in Tarjan's algorithm 
bool InStack[M];              //check if it is in the stack 
int DFN[M];                   //depth-first search Access order 
int Low[M];                   //The earliest order that can be traced back 
int Comnumber;         //Number of strongly connected components of directed graph 
int Index;                  //Index number 
vector < int > Edge[M];         //Adjacency list Represents 
vector < int > Com[M];    //Get the result of the strongly connected component 
int belong[M]; //Give each strongly connected component number that marks him 
int in[M];//Record the incoming edge of each connected component 
int sta[ 100005 ],to[ 100005 ],c[ 100005 ];   //Record each edge, then you can use On to find the smallest incoming edge of each strongly connected component, or out side 
void  Tarjan ( int i)
 {
     int j;
    DFN[i]=Low[i]=Index++;
    InStack[i]=true;
    STACK[++top]=i;
    for (int e=0;e<Edge[i].size();e++){
        j=Edge[i][e];
        if (DFN[j]== -1 ){   //Not visited
            Tarjan(s);
            Low[i]=min(Low[i],Low[j]);
        }
        else if (InStack[j])
            Low[i]=min(Low[i],DFN[j]);   //In this layer of recursion. Low[j] has not been updated yet. To be reasonable, there is no difference between writing DFN and LOW j here.
    }
    if (DFN[i]==Low[i])
    {
        Comnumber++;
        do
        {
            j=STACK[top--];
            InStack[j]=false;
            belong[j]=Comnumber;
        }
        while (j!=i);
    }
}

void  solve ( int N)      //The number of points in this graph, note that it is 0-indexed! 
{
    Comnumber=0;
    top=0;
    Index=1;
    memset(STACK,-1,sizeof(STACK));
    memset(InStack,0,sizeof(InStack));
    memset(DFN,-1,sizeof(DFN));
    memset(Low,-1,sizeof(Low));
    for(int i=1;i<=N;i++)
        if(DFN[i]==-1)
            Tarjan(i);
}
//Idea: 
//Firstly, the number of points is reduced and counted on the strongly connected components 
int  main () {
     int n,m;
     //freopen("1.txt","r",stdin); 
    while (~ scanf ( "%d %d" ,&n,&m)){
         for ( int i= 1 ;i<=M;i++){
             Edge[i].clear();
        }
        for(int i=1;i<=m;i++){
            scanf("%d %d %d",&sta[i],&to[i],&c[i]);
            stands [i] ++;
            to[i]++;
            Edge[sta[i]].push_back(to[i]);
        }
        solve(n);
            in[i]=100001;
        }
        for(int i=1;i<=m;i++){
            int u=sta[i],v=to[i],C=c[i];
            if(belong[u]!=belong[v]){
                in[belong[v]]=min(in[belong[v]],C);
            }
        }
        int ans=0;
        for(int i=1;i<=Comnumber && i!=belong[1] ;i++){
            if(in[i]!=100001)
                ans+=in[i];
        }
        printf("%d\n",ans);
    }
    return 0;
}

The second question:
hdu 4635
http://acm.hdu.edu.cn/showproblem.php?pid=4635
The meaning of the
question: The meaning of the question is concise: For a directed simple graph (no multiple edges, no self-loops), ask How many edges can be added at most so that the whole graph is still a simple directed graph, but the whole graph is not strongly connected!

2016-5-10 Review:
T2: In the first step, the block that is already a strongly connected component is reduced to a point (and some edges can be added), and there must be a “point” with an in-degree of 0 or an out-degree for the remaining graph. The degree is 0, otherwise it must be strongly connected, and then this point does not move, and other points form a complete graph, which should be the most edges. It is reasonable to write this way. It is not complicated and can be A quickly. Still young
Oh , after reading the positive solution, I found that I was still too young, and I overlooked a place: “for the points we isolate” must be the block with the least number of points, right, because this is the edge deleted in the entire complete graph. It is the least, and then it is also considered that the initially given edge cannot be deleted, so you should find a strongly connected block with “out-degree 0 or in-degree 0” in the “initial graph” and “contains the least number of points” ,
this

This problem can retain the idea of ​​these problems is actually very simple: For the graph given at the beginning (m edges are given at the beginning), there must be some strongly connected components, and we can regard the strongly connected components as points.

Then for this graph, if we want to keep the whole not strongly connected, we only need to exclude one point (strongly connected component): That is, this point has no incoming edge, or no outgoing edge, and the whole graph is not strongly connected if a condition is satisfied pictured.

If there are n points, then there are n(n-1) edges for the complete graph, and
m edges are given at the beginning, so ans=n
(n-1) -m;
then how do we find the strongly connected components Woolen cloth? Naturally, we can find the strongly connected component that contains the least number of points, and delete its incoming or outgoing edges (the two are actually equal in number of edges).
So ans -= v*(nv);

Think about it carefully, right? Is it a mistake? I made a wa in this place. Yes, we did not realize that the m edges given at the beginning may have both incoming and outgoing edges for the component containing the smallest point. At this time, this strong connection Quantities cannot be deleted in any way.
So we have to find the component with the smallest point among the strongly connected components whose incoming or outgoing edge is 0 among the edges given at the beginning.

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
using namespace std;
#define   M 100005               //Maximum possible number of points in the title
 int STACK[M],top;           //stack in Tarjan's algorithm 
bool InStack[M];              //check if it is in the stack 
int DFN[M];                   //depth-first search Access order 
int Low[M];                   //The earliest order that can be traced back 
int Comnumber;         //Number of strongly connected components of directed graph 
int Index;                  //Index number 
vector < int > Edge[M];         //Adjacency list Represents 
vector < int > Com[M];    //Get the result of strongly connected components 
int in[M];   
 int out[M];
 int num[M];//Number each strongly connected component that marks him = belong 
void  Tarjan ( int i)
 {
     int j;
    DFN[i]=Low[i]=Index++;
    InStack[i]=true;
    STACK[++top]=i;
    for (int e=0;e<Edge[i].size();e++){
        j=Edge[i][e];
        if (DFN[j]== -1 ){   //Not visited
            Tarjan(s);
            Low[i]=min(Low[i],Low[j]);
        }
        else if (InStack[j])
            Low[i]=min(Low[i],DFN[j]);   //In this layer of recursion. Low[j] has not been updated yet. To be reasonable, there is no difference between writing DFN and LOW j here.
    }
    if (DFN[i]==Low[i])
    {
        //cout<<"TT    "<<i<<"   "<<Low[i]<<endl;
        Comnumber++;
        do
        {
            j=STACK[top--];
            InStack[j]=false;
            num[j]=Comnumber;
            Com[Comnumber].push_back(j);
        }
        while (j!=i);
    }
}

void  solve ( int N)      //The number of points in this graph, note that it is 0-indexed! 
{
    Comnumber=0;
    top=0;
    Index=1;
    memset(STACK,-1,sizeof(STACK));
    memset(InStack,0,sizeof(InStack));
    memset(DFN,-1,sizeof(DFN));
    memset(Low,-1,sizeof(Low));
    memset(num,-1,sizeof(num));
    memset(out,0,sizeof(out));
    memset(in,0,sizeof(in));
    for(int i=1;i<=N;i++)
        if(DFN[i]==-1)
            Tarjan(i);
}
int main(){
    int t;
    int n,m;
    //freopen("1.txt","r",stdin);
    scanf("%d",&t);
    for(int k=1;k<=t;k++){
        for(int i=1;i<=M;i++)
            Edge[i].clear();
        for(int i=1;i<=M;i++)
               Com[i].clear();
        printf("Case %d: ",k);
        scanf("%d %d",&n,&m);
        for(int i=1;i<=m;i++){
            int sta,to;
            cin>>sta>>to;
            Edge[sta].push_back(to);
        }
        solve(n);
//        printf("Comnumber=%d\n",Comnumber);
        if(Comnumber==1){
            printf("-1\n");
            continue;
        }
        __int64 from= 100005 ;

         for ( int i= 1 ;i<=n;i++)
                for ( int j= 0 ;j<Edge[i].size();j++)
                     if (num[i]!=num[Edge[i][j ]])    //If the two points are not in the same connected component
                    {
                        out[num[i]]++;
                        in[num[Edge[i][j]]]++;
                    }

         for(int i=1;i<=Comnumber;i++)
         {
             if(in[i]==0||out[i]==0)
             {
                  if( (__int64)Com[i].size() < minn)
                      minn=(__int64)Com[i].size();
             }
         }
        __int64 ans=(__int64)n*(n-1);
        ans-=(__int64)m;
        ans-=(__int64)( (n-from)*from);
        printf("%I64d\n",ans);
    }
    return 0;
}

This problem of poj 2366
contains two very classic problems:
1. For a directed graph, at least a few documents need to be sent so that the document can be transmitted to every point.
That is to find a few connected blocks with an in-degree of 0, and send a few copies if there are a few

  1. For a directed graph, add at least a few edges to make it a strongly connected graph (reachable to each other)
    . Solution to the second problem:
    If the graph itself is a strongly connected graph, then don’t add it.
    Otherwise, the added edge is max(number of blocks with in-degree 0, number of blocks with out-degree 0). Why is taking the maximum value the side that needs to be added?
    It is necessary to add a few edges to the DAG to make the DAG strongly connected. The answer to question 2 is how many. The method of
    adding edges:
    add an in-edge for each point whose in-degree is 0, and add an in-edge for each point whose out-degree is 0. Add out edges from the points of .
    Assuming there are n points with in-degree 0 and m points with out-degree 0, how to add edges?
    Put all the points with in-degree 0 numbered 0, 1, 2, 3, 4 ….N -1
    each time an out-degree 0 point reachable by an in-degree 0 point numbered i, add an out-edge, connect to The out-degree 0 point numbered (i+1)%N
    needs to add n edges.
    If m <= n,
    after adding these n edges, there is no in-degree 0 point, then the problem is solved, adding a total of If there are n edges,
    if m > n, then there are mn in-degree 0 points, then take any point other than these points, and connect all these points to the upper edge, then you can add mn edges.
    So, max(m,n) is the solution to the second problem

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
using namespace std;
#define   M 110              //Maximum possible number of points in the title
 int STACK[M],top;           //stack in Tarjan's algorithm 
bool InStack[M];              //check if it is in the stack 
int DFN[M];                   //depth-first search Access order 
int Low[M];                   //The earliest order that can be traced back 
int Comnumber;         //Number of strongly connected components of directed graph 
int Index= 0 ;                  //Index number 
int belong[M]; //For each Mark his strongly connected component number 
vector < int > Edge[M];         //The adjacency list represents 
vector < int > Com[M];    //Get the result of the strongly connected component 
intin[M];
 int out[M];    //Store the out-degree of each strongly connected component, in-degree 
void  Tarjan ( int i)
 {
     int j;
    DFN[i]=Low[i]=Index++;
    InStack[i]=true;
    STACK[++top]=i;
    for (int e=0;e<Edge[i].size();e++){
        j=Edge[i][e];
        if (DFN[j]==-1){
            Tarjan(s);
            Low[i]=min(Low[i],Low[j]);
        }
        else if (InStack[j])
            Low[i]=min(Low[i],DFN[j]);   //In this layer of recursion. Low[j] has not been updated yet. To be reasonable, there is no difference between writing DFN and LOW j here.
    }
    if (DFN[i]==Low[i])
    {
        //cout<<"TT    "<<i<<"   "<<Low[i]<<endl;
        Comnumber++;
        do
        {
            j=STACK[top--];
            InStack[j]=false;
            Com[Comnumber].push_back(j);
            belong[j]=Comnumber;
        }
        while (j!=i);
    }
}

void  solve ( int N)      //The number of points in this graph, note that it is 0-indexed! 
{
    Comnumber=0;
    top=0;
    Index=1;
    memset(STACK,-1,sizeof(STACK));
    memset(InStack,0,sizeof(InStack));
    memset(in,0,sizeof(in));
    memset(out,0,sizeof(out));
    memset(DFN,-1,sizeof(DFN));
    memset(Low,-1,sizeof(Low));
    for(int i=1;i<=N;i++)
        if(DFN[i]==-1)
            Tarjan(i);
}
void init(){
    for(int i=1;i<=M;i++){
        Edge[i].clear();
        Com[i].clear();
    }
}
/*
The basis for this algorithm to work properly is that the graph is 1-indexed.
*/
int main(){
    int n;
    freopen("1.txt","r",stdin);
    while(~scanf("%d",&n)){
        init();
        for(int i=1;i<=n;i++){
            int tem;
            while(~scanf("%d",&tem) &&tem){
                Edge[i].push_back(tem);
            }
        }
        solve(n);
        for ( int i= 1 ;i<=n;i++){
             int len=( int )Edge[i].size();
             for ( int j= 0 ;j<len;j++){
                 int u=i,v =Edge[i][j];
                 if (belong[u] != belong[v]){   //Damn, I forgot to write this
                    in[ belong[v] ]++;
                    out[belong[u] ]++;
                }
            }
        }
        int ans1=0;
        int ans2=0;
        if(Comnumber==1){
            printf("1\n0\n");
            continue;
        }
        for(int i=1;i<=Comnumber;i++){
            if(in[i]==0){
                ans1++;
            }
            if(out[i]==0)
                ans2++;
        }
        ans2=max(ans1,ans2);
        printf("%d\n",ans1);
        printf("%d\n",ans2);
    }
}

Leave a Comment

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