Cod sursa(job #2199386)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 27 aprilie 2018 15:21:41
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 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;
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()
{ int x, y;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;
}