Pagini recente » Cod sursa (job #1950246) | Cod sursa (job #938108) | Cod sursa (job #967828) | Cod sursa (job #2195733) | Cod sursa (job #2980011)
#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 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);
}
}
inline void empty ()
{
for (int i=1; i<=n; i++) u[i]=0;
}
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;
}
}
}
inline void afis()
{
fout << nrctc <<"\n";
for (int i=1; i<=nrctc; ++i) {
for (int j=1; j<=n; ++j) if (CTC[j]==i) fout<<j<<' ';
fout<<'\n';
}
}
int main()
{
citire();
solve();
afis();
return 0;
}