Pagini recente » Cod sursa (job #2905784) | Cod sursa (job #2258273) | Cod sursa (job #1101644) | Cod sursa (job #2715482) | Cod sursa (job #1347961)
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 100099
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N, M, viz[NMAX], Tsort[NMAX], sol,x, y;
vector < int > G[NMAX], T[NMAX], CTC[NMAX];
void DFS(int node)
{
viz[node]=1;
for (vector<int>::iterator it=G[node].begin(); it!=G[node].end(); it++)
if(!viz[*it]) DFS(*it);
Tsort[++Tsort[0]]=node;
}
void DFS_T(int node)
{
viz[node]=0; CTC[sol].push_back(node);
for (vector<int>::iterator it=T[node].begin(); it!=T[node].end(); it++)
if(viz[*it]) DFS_T(*it);
}
void GetCTC()
{
for (int i=1; i <=N; i++)
if(!viz[i]) DFS(i);
for(int i=N; i>=1; --i)
if(viz[Tsort[i]])
++sol, DFS_T(Tsort[i]);
}
int main()
{
f>>N>>M;
for(int i=1; i<=M;i++)
f>>x>>y, G[x].push_back(y), T[y].push_back(x);
GetCTC();
g<<sol<<'\n';
for (int i=1; i<=sol; i++)
{
for (vector<int>::iterator it=CTC[i].begin(); it!=CTC[i].end(); it++)
g<<*it<<' ';
g<<'\n';
}
f.close();g.close();
return 0;
}