Pagini recente » Cod sursa (job #467946) | Cod sursa (job #2946054) | Cod sursa (job #2364472) | Cod sursa (job #2255868) | Cod sursa (job #2929751)
#include <bits/stdc++.h>
#include <iostream>
#define MAX 100001
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
stack <int> S;
vector<int> graf[MAX],grafT[MAX],CTC[MAX];
int N, M, NrCTC;
int vizitat[MAX];
void Read()
{
f >> N >> M;
for(int i = 1; i <= M; i++)
{
int x,y;
f >> x >> y;
graf[x].push_back(y); // Construim graful G
grafT[y].push_back(x); // Construim transpusa grafului G
}
}
void DFS_graf(int Nod)
{
vizitat[Nod] = 1;
for(int i=0; i<graf[Nod].size();i++) {
int Vecin = graf[Nod][i];
if(!vizitat[Vecin])
DFS_graf(Vecin);
}
S.push(Nod);
}
void DFS_graf_T(int Nod)
{
vizitat[Nod] = 2;
CTC[NrCTC].push_back(Nod);
for(int i=0; i<grafT[Nod].size();i++) {
int Vecin = grafT[Nod][i];
if(vizitat[Vecin]==1)
DFS_graf_T(Vecin);
}
}
void Solve()
{
for(int i=1;i<=N;i++)
if(!vizitat[i])
DFS_graf(i);
while(!S.empty()) {
int Nod = S.top();
if (vizitat[Nod] == 1) {
NrCTC++;
DFS_graf_T(Nod);
}
S.pop();
}
}
void Print()
{
cout << NrCTC <<"\n";
for(int i = 1; i <= NrCTC; i++) {
for(unsigned int j = 0; j < CTC[i].size(); j++)
cout << CTC[i][j] <<" ";
cout<<"\n";
}
}
int main()
{
Read();
Solve();
Print();
return 0;
}