Pagini recente » Cod sursa (job #794759) | Cod sursa (job #1018380) | Monitorul de evaluare | Rating Sabina Brasoveanu (sabinab) | Cod sursa (job #2979989)
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define N 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> Graf[N],GrafT[N];
int n,m,nrctc,u[N],CTC[N];
set <int> S1,S2;
void empty ()
{
for (int i=1; i<=n; i++) u[i]=0;
}
void citire()
{
fin >> n >> m;
for(int i = 1; i <= m; i++)
{
int x,y;
fin >> x >> y;
Graf[x].push_back(y);
GrafT[y].push_back(x);
}
}
void dfsGraf(int x)
{
u[x]=1;
S1.insert(x);
for(int i=0; i<Graf[x].size(); i++)
{
int y = Graf[x][i];
if(!u[y])
dfsGraf(y);
}
}
void dfsGrafT(int x)
{
u[x]=1;
S2.insert(x);
for(int i=0; i<GrafT[x].size(); i++)
{
int y = GrafT[x][i];
if(!u[y])
dfsGrafT(y);
}
}
void solve()
{
for(int i=1; i<=n; i++)
if(!CTC[i])
{
S1.clear ();
S2.clear ();
nrctc++;
empty();
dfsGraf(i);
empty();
dfsGrafT(i);
for (set<int>::iterator it=S1.begin(); it!=S1.end(); ++it)
{
if (S2.count(*it)) CTC[*it]=nrctc;
}
}
}
void afis()
{
fout << nrctc <<"\n";
for (int i=1; i<=nrctc; i++) {
for (int j=1; j<=n; j++) if (CTC[j]==i) out<<j<<' ';
out<<'\n';
}
}
int main()
{
citire();
solve();
afis();
return 0;
}