POJ 2762 单连通图

题意：

给你一个有向图，问你这个图是不是单连通图，单连通就是任意两点之间至少存在一条可达路径。

思路：

先强连通所点，重新建图，此时的图不存在环，然后我们在看看是否存在一条路径可以吧所有点都覆盖了就行了，直接一遍拓扑排序，只要拓扑排序唯一就行了，拓扑排序唯一的条件是每次最多只能有一个进队。

#include<stdio.h>

#include<string.h>

#include<queue>

#include<stack>

#include<map>

#define N_node 1005

#define N_edge 6500

#define INF 1000000000

using namespace std;

typedef struct

{

   int to ,next;

}STAR;

typedef struct

{

   int a ,b;

}EDGE;

STAR E[N_edge] ,E1[N_edge] ,E2[N_edge];

EDGE edge[N_edge];

map<int ,map<int ,int> >mk_map;

stack<int>sk;

int list[N_node] ,list1[N_node] ,list2[N_node] ,tot;

int Belong[N_node] ,cnt;

int in[N_node] ,out[N_node];

int mark[N_node];

void add(int a ,int b)

{

   E1[++tot].to = b;

   E1[tot].next = list1[a];

   list1[a] = tot;

   E2[tot].to = a;

   E2[tot].next = list2[b];

   list2[b] = tot;

}

void _add(int a ,int b)

{

   E[++tot].to = b;

   E[tot].next = list[a];

   list[a] = tot;

}

void DFS_1(int s)

{

   mark[s] = 1;

   for(int k = list1[s] ;k ;k = E1[k].next)

   {

      int xin = E1[k].to;

      if(!mark[xin])

      DFS_1(xin);

   }

   sk.push(s);

}

void DFS_2(int s)

{

   mark[s] = 1;

   Belong[s] = cnt;

   for(int k = list2[s] ;k ;k = E2[k].next)

   {

      int xin = E2[k].to;

      if(!mark[xin])

      DFS_2(xin);

   }

}

bool TP_sort(int n)

{

   queue<int>q;

   int ss = 0;

   for(int i = 1 ;i <= n ;i ++)

   {

      if(in[i] == 0)

      {

         q.push(i);

         ss ++;

         if(ss > 1) return 0;

      }

   }

   int sot = 0;

   while(!q.empty())

   {

      int xin ,tou;

      tou = q.front();

      q.pop();

      sot ++;

      ss = 0;

      for(int k = list[tou] ;k ;k = E[k].next)

      {

         xin = E[k].to;

         if(--in[xin] == 0)

         {

            ss ++;

            q.push(xin);

            if(ss > 1) return 0;

         }

      }

   }

   return sot == n;

}

int main ()

{

   int t ,n ,m;

   int a ,b ,i;

   scanf("%d" ,&t);

   while(t--)

   {

      scanf("%d %d" ,&n ,&m);

      memset(list1 ,0 ,sizeof(list1));

      memset(list2 ,0 ,sizeof(list2));

      tot = 1;

      for(i = 1 ;i <= m ;i ++)

      {

         scanf("%d %d" ,&a ,&b);

         add(a ,b);

         edge[i].a = a ,edge[i].b = b;

      }

      memset(mark ,0 ,sizeof(mark));

      while(!sk.empty())sk.pop();

      for(int i = 1 ;i <= n ;i ++)

      if(!mark[i]) DFS_1(i);

      cnt = 0;

      memset(mark ,0 ,sizeof(mark));

      while(!sk.empty())

      {

         int xin = sk.top();

         sk.pop();

         if(mark[xin]) continue;

         cnt ++;

         DFS_2(xin);

      }

      mk_map.clear();

      memset(in ,0 ,sizeof(in));

      memset(out ,0 ,sizeof(out));

      memset(list ,0 ,sizeof(list));

      tot = 1;

      for(i = 1 ;i <= m ;i ++)

      {

         a = Belong[edge[i].a];

         b = Belong[edge[i].b];

         if(a == b || mk_map[a][b]) continue;

         mk_map[a][b] = 1;

         in[b] ++ ,out[a] ++;

         _add(a ,b);

      }

      if(TP_sort(cnt)) puts("Yes");

      else puts("No");

   }

   return 0;

}

巴特西

POJ 2762 单连通图

最新文章

热门文章