Cod sursa(job #2475637)

Utilizator mionelIon. M mionel Data 17 octombrie 2019 11:40:21
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> L[100001], C[100001], CTC[100001];
int n, m, Viz[100001],nrc;
stack <int> S;
void Citire()
{ int i , x, y;
    f>>n>>m;
    for(i=1;i<=m;i++)
    { f>>x>>y;
        L[x].push_back(y);
        C[y].push_back(x);
    }
}
inline void DFS(int nod)
{ Viz[nod]=1;
int j, vec;
    for(j=0;j<L[nod].size();j++)
    { vec=L[nod][j];
        if(Viz[vec]==0)
            DFS(vec);
    }
  S.push(nod);
}
inline void DFS2(int nod)
{ Viz[nod]=1;
  int j ,vec;
  for(j=0;j<C[nod].size();j++)
  { vec=C[nod][j];
    if(Viz[vec]==0)
      DFS2(vec);
  }
  CTC[nrc].push_back(nod);
}
void Afisare()
{ int i, j;
g<<nrc<<endl;
    for(i=1;i<=nrc;i++)
      {for(j=0;j<CTC[i].size();j++)
       g<<CTC[i][j]<<" ";
       g<<"\n";
      }
}
int main()
{int i,nod;
Citire();
for(i=1;i<=n;i++)
    if(Viz[i]==0)
    DFS(i);
memset(Viz, 0, sizeof(Viz));
while(!S.empty())
{ nod=S.top();
 S.pop();
  if(Viz[nod]==0)
    { //sort(CTC[nrc].begin(), CTC[nrc].end());
    nrc++;
    DFS2(nod);}
}
Afisare();

f.close();
g.close();
    return 0;
}