Cod sursa(job #1962936)

Utilizator dorupopDoru Pop dorupop Data 12 aprilie 2017 10:12:40
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <cstdio>
#include <bitset>
#include <vector>

#define NMAX 100001
#define INF (1 << 30)

using namespace std;
bool viz[NMAX];
vector<int> G[NMAX];
vector<int> GT[NMAX];
vector<vector<int> > solution;
vector<int> sol[NMAX];
int n, m, count, index[NMAX], minim[NMAX],k,nr;
int st[NMAX];
void readInput() {
  freopen("ctc.in", "r", stdin);
  freopen("ctc.out", "w", stdout);
  int a, b;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &a, &b);
    G[a].push_back(b);
     GT[b].push_back(a);

  }

  }


void dfs(int nod){
int i;
viz[nod]=1;
for(i=0;i<G[nod].size();i++)
    if(viz[G[nod][i]]==0){
        dfs(G[nod][i]);

    }
k++;
st[k]=nod;
    }


void dfst(int nod){
   int i;
   sol[nr].push_back(nod);
   viz[nod]=0;
   for(i=0;i<GT[nod].size();i++)
       if(viz[GT[nod][i]]==1)
           dfst(GT[nod][i]);
}



int main() {
  readInput();

 for(int i=1;i<=n;i++){
    if(viz[i]==0)
       dfs(i);

 }
 while(k>0){
     while(k>0&&viz[st[k]]==0)
        k--;
  if(k>0){
      nr++;
        dfst(st[k]);
    }
 }
    printf("%d\n",nr);
    for(int i=1;i<=nr;i++){
        for(int j=0;j<sol[i].size();j++)
            printf("%d ",sol[i][j]);
         printf("\n");
    }

  return 0;
}