Cod sursa(job #2084768)

Utilizator eduardandrei20Nechifor Eduard Andrei eduardandrei20 Data 9 decembrie 2017 11:51:55
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <bits/stdc++.h>
#define NN 100001
using namespace std;
stack<int>st;
vector<int>v;
int n , m ,componente;
bool used[NN],viz[NN];
struct nod
{
    int info ;
    nod *next;
}*G[100001], *GT[100001];

void add_G( int x, int y )
{
    nod * aux = new nod ;
    aux -> info = y ;
    aux -> next = G[x];
    G[x] = aux ;
}
void add_GT( int x, int y )
{
    nod * aux = new nod ;
    aux -> info = y ;
    aux -> next = GT[x];
    GT[x] = aux ;
}
void scan()
{
    freopen("ctc.in","r",stdin);
    scanf ("%d%d" , &n , &m) ;
    for ( int i = 1; i<= m ; ++ i )
    {
        int x ,y ;
        scanf("%d%d",&x,&y);
        add_G(x,y);
        add_GT(y,x);
    }
}
void first_dfs( int node )
{
    used [node] = true ;
      for ( nod * aux =G[node]; aux ; aux = aux ->next)
        if(!used[aux->info])first_dfs(aux->info);
         st.push(node);
}
void dfs(int node )
{ v.push_back(node);
    viz[node]=true ;
     for ( nod * aux = GT[node]; aux ; aux = aux ->next)
        if(!viz[aux->info])dfs(aux->info);

}



int main()
{
    scan();
    for ( int i = 1 ; i <= n ; ++ i )
          if(!used[i]) first_dfs(i);
               // in stack am valorile in ordinea timpilor de finish
           while(!st.empty())
           {
               if(viz[st.top()])st.pop();
                else { componente ++ ;
                       dfs(st.top());
                       v.push_back(0);
                     }
           }
  freopen("ctc.out","w",stdout);
           for ( int i = 0 ; i < v.size() ; ++ i )
            {
                if(v[i]==0)printf("\n");
                else printf("%d ",v[i]);
            }

    return 0;
}