Cod sursa(job #2369831)

Utilizator Luca19Hritcu Luca Luca19 Data 6 martie 2019 09:25:16
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <vector>
#include <stack>
#define Nmax 100005

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

vector <int> v1[Nmax], v2[Nmax], v3[Nmax];
int seen[Nmax];
stack <int> st;
int n, m, x, y;
int num_ctc = 0;
vector <int> ::iterator it;

void first_DFS(int node)
{
    seen[node] = 1;
     for ( int i = 0, l = v1[node].size() ; i < l ; i ++ )
      {
          int nnode = v1[node][i];
          if( seen[nnode] != 0)
            continue;
          first_DFS(nnode);
      }
    st.push(node);
}

void second_DFS(int node)
{
     seen[node] = -1;
    for ( int i = 0, l = v2[node].size(); i < l ; i ++ )
     {
         int nnode = v2[node][i];
         if( seen[nnode] == -1 )
            continue;
         second_DFS(nnode);
     }
     v3[num_ctc].push_back(node);
}

int main()
{
    f >> n >> m ;
    while ( m -- )
    {
        f >> x >> y;
        v1[x].push_back(y);
        v2[y].push_back(x);
    }
    for ( int i = 1 ; i <= n ; i ++ )
     if(!seen[i])
        first_DFS(i);

    while(!st.empty())
    {
        if( seen[st.top()] == -1 )
        {
            st.pop();
            continue;
        }
        num_ctc++;
       second_DFS(st.top());
        st.pop();
    }
      g << num_ctc << '\n';
    for ( int i = 1 ; i <= num_ctc ; i ++ )
     {
       for ( it = v3[i].begin() ; it != v3[i].end() ; it ++ )
            g << *it << " ";
            g << '\n';

     }
        return 0;
}