Pagini recente » Cod sursa (job #1144828) | Istoria paginii runda/test193120947281 | Cod sursa (job #2144074) | Cod sursa (job #1152080) | Cod sursa (job #1091258)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
fstream fin("ctc.in", ios::in);
fstream fout("ctc.out", ios::out);
vector <int> graph[100000], graphT[100000], comp[100000];
int k=0, stock[100000];
bool vizitat[100000];
int N, M;
void citire()
{
int x, y;
fin>>N;
fin>>M;
int NrE=M;
while(NrE--)
{
fin>>x>>y;
graph[x].push_back(y);
graphT[y].push_back(x);
}
}
void dfs1(int x)
{
vizitat[x]=true;
for(int i=0; i<graphT[x].size(); i++)
{
if(!vizitat[graphT[x][i]])
dfs1(graphT[x][i]);
}
stock[++stock[0]]=x;
}
void dfs2(int x)
{
vizitat[x]=true;
for(int i=0; i<graph[x].size(); i++)
{
if(!vizitat[graph[x][i]])
dfs2(graph[x][i]);
}
comp[k].push_back(x);
}
void SortareTop()
{
for(int i=1; i<=N; i++)
if(!vizitat[i])
dfs1(i);
}
int main()
{
citire();
SortareTop();
memset(vizitat, false, sizeof(vizitat));
for(int i=N; i>0; i--)
{
if(!vizitat[stock[i]])
{
k++;
dfs2(stock[i]);
}
}
fout<<k<<endl;
for(int i=1; i<=k; i++)
{
for(int j=0; j<comp[i].size(); j++)
fout<<comp[i][j]<<" ";
fout<<endl;
}
return 0;
}