Cod sursa(job #2220310)

Utilizator tiberiu392Tiberiu Ungurianu tiberiu392 Data 11 iulie 2018 12:30:21
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 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 = 1 , 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 = 1 , 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 <= n ; i++ )
        {
       for ( it=v3[i].begin() ; it != v3[i].end() ; it ++ )
          g << *it << " ";
       g << '\n';

     }
    return 0;
}