Pagini recente » Monitorul de evaluare | Cod sursa (job #2293636) | Cod sursa (job #210452) | Cod sursa (job #696607) | Cod sursa (job #2929104)
#include <iostream>
#include <fstream>
#include <vector>
#include<stack>
#define NMAX 100002
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M, nrCTC;
int vizitat[NMAX];
stack<int> s;
vector<int> graf[NMAX], transpus[NMAX], ctc[NMAX];
void citire()
{
fin>>N>>M;
for(int i = 0; i < M; ++i)
{
int u,v;
fin>>u>>v;
graf[u].push_back(v);
transpus[v].push_back(u); ///construiesc graful transpus
}
}
void DFSP(int x)
{
vizitat[x] = 1;
for(int i = 0; i < graf[x].size(); ++i)
{
int adj = graf[x][i];
if(!vizitat[adj])
DFSP(adj);
}
s.push(x);
}
void DFSM(int x)
{
vizitat[x] = -1;
ctc[nrCTC].push_back(x);
for(int i = 0; i < transpus[x].size(); ++i)
{
int adj = transpus[x][i];
if(vizitat[adj] == 1)
DFSM(adj);
}
}
void solutie()
{
for(int i = 1; i <= N; ++i)
if(!vizitat[i])
DFSP(i);
while(!s.empty())
{
int nod = s.top();
if(vizitat[nod] == 1)
{
++nrCTC;
DFSM(nod);
}
s.pop();
}
}
void afisare()
{
fout<<nrCTC<<"\n";
for(int i = 1; i <= nrCTC; ++i)
{
for(int j = 0; j < ctc[i].size(); ++j)
fout<<ctc[i][j]<<" ";
fout<<"\n";
}
}
int main()
{
citire();
solutie();
afisare();
return 0;
}