Алгоритмы на графах

Vladimir Sitnikov - 02 Apr 2004

/*
Формат входных данных:
[Число вершин в графе]
[Число ребер, входящих из вершины (вершина номер 0)] [номер вершины, куда ведет связь] [номер вершины, куда ведет связь]
[Число ребер, входящих из вершины (вершина номер 1)] [номер вершины, куда ведет связь] [номер вершины, куда ведет связь]
...
Sample intput:
5
1 1
2 2 3
1 0
1 4
1 3
Sample output:
1 1
2 1
0 1
4 2
3 2
*/
#include <stdio.h>

int N;                // Количество вершин в графе
#define MAX_NODES 100 // Максимальное количество вершин
#define MAX_EDGES 10  // Максимальное количество ребер, выходящих из одной вершины

int edges[MAX_NODES][MAX_EDGES]; // Граф, в котором ищем сильно связные компоненты
int edges_c[MAX_NODES];

int edgesT[MAX_NODES][MAX_EDGES]; // Транспонированый граф
int edgesT_c[MAX_NODES];

int state[MAX_NODES];             // Иcпользуется в поиске для того, чтобы отмечать посещенные вершины

int f[MAX_NODES],last_f=0;        // Список предварительной расстановки вершин

int c=1; // Номер компоненты (увеличиваем его, когда находим новую)

void dfs(int node){
   state[node]=1;

   for(int i=0; i<edges_c[node]; i++) // Самый обыкновенный поиск в глубину.
      if (state[edges[node][i]]==0)
         dfs(edges[node][i]);

   f[last_f++]=node;         
}

void dfsT(int node){
   state[node]=1;

   for(int i=0; i<edgesT_c[node]; i++) // Самый обыкновенный поиск в глубину в транспонированном графе.
      if (state[edgesT[node][i]]==0)   
         dfsT(edgesT[node][i]);         

   printf("%d %d\n",node,c);
}

void scc(){ // Strongly Connected Components - функция выделения сильно связных компонент графа
   int i;
   for(i=0; i<N; i++) state[i]=0;

   for(i=0; i<N; i++)               
      if (state[i]++==0)   
         dfs(i);   

   for(i=0; i<N; i++) state[i]=0;

   for(last_f--; last_f>=0; last_f--)
      if (state[f[last_f]]==0){      
         dfsT(f[last_f]);               
         c++;      
      }
}

int main(){
   int i;

   scanf("%d",&N);
   for(i=0; i<N; i++) edges_c[i]=edgesT_c[i]=0;
   
   for(i=0; i<N; i++){
      int j;
      scanf("%d",&edges_c[i]);
      for(j=0; j<edges_c[i]; j++){
         int to;
         scanf("%d",&to);
         edges[i][j]=to;
         edgesT[to][edgesT_c[to]++]=i;
      }
   }

   scc();

   return 0;
}