Cod sursa(job #1455517)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 28 iunie 2015 10:50:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int Dim = 100001;

vector<int> G[Dim], TG[Dim], SCC[Dim];
int N,M,K,Nr;
int F[Dim];
bool V[Dim];

void DFS1(int Node)
{
    V[Node] = 1;

    for (int i = 0;i < G[Node].size();i++)
        if (!V[G[Node][i]])
                     DFS1(G[Node][i]);
    F[++Nr] = Node;
}

void DFS2(int Node)
{
    V[Node] = 1;

    SCC[K].pb(Node);

    for (int i = 0;i < TG[Node].size();i++)
        if (!V[TG[Node][i]])
                      DFS2(TG[Node][i]);
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);

     scanf("%d %d",&N,&M);

     for (int i = 1;i <= M;i++)
     {
         int A,B;
         scanf("%d%d",&A,&B);
         G[A].pb(B);
         TG[B].pb(A);
     }

     for (int i = 1;i <= N;i++)
        if (!V[i])
                  DFS1(i);

    memset(V,0,sizeof(V));

    for (int i = Nr;i > 0;i--)
        if (!V[F[i]])
        {
            K++;
            DFS2(F[i]);
        }

    printf("%d\n",K);

    for (int i = 1;i <= K;i++)
    {
        for (int j = 0;j < SCC[i].size();j++)
              printf("%d ",SCC[i][j]);

        printf("\n");
    }

  return 0;
}