Pagini recente » Cod sursa (job #2575259) | Monitorul de evaluare | Cod sursa (job #3154091) | Cod sursa (job #1369682) | Cod sursa (job #1069117)
#include<fstream>
#include<bitset>
#include<vector>
#define Nmax 100099
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N,M,sol,Topologic[Nmax];
vector < int > Graph[Nmax],Transpus[Nmax],Comp[Nmax];
bitset < Nmax > viz;
void DFS(int nod)
{
viz[nod]=1;
vector < int > :: iterator it;
for(it=Graph[nod].begin();it!=Graph[nod].end();++it)
if(!viz[*it])DFS(*it);
Topologic[++Topologic[0]]=nod;
}
void DFST(int nod)
{
viz[nod]=0;
Comp[sol].push_back(nod);
vector < int > :: iterator it;
for(it=Transpus[nod].begin();it!=Transpus[nod].end();++it)
if(viz[*it])DFST(*it);
}
int main()
{
f>>N>>M;
for(int i=1;i<=M;++i)
{
int x,y;
f>>x>>y;
Graph[x].push_back(y);
Transpus[y].push_back(x);
}
for(int i=1;i<=N;++i)
if(!viz[i]) DFS(i);
for(int i=N;i>=1;--i)
if(viz[Topologic[i]])
{
++sol;
DFST(Topologic[i]);
}
g<<sol<<'\n';
for(int i=1;i<=sol;++i,g<<'\n')
for(int j=0;j<Comp[i].size();++j)g<<Comp[i][j]<<' ';
f.close();g.close();
return 0;
}