Pagini recente » Cod sursa (job #1721987) | Cod sursa (job #285012) | Cod sursa (job #3128763) | Cod sursa (job #917399) | Cod sursa (job #1091270)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
int const N_MAX=100000;
fstream fin("ctc.in", ios::in);
fstream fout("ctc.out", ios::out);
vector <int> graph[N_MAX], graphT[N_MAX], comp[N_MAX];
int k=0, stock[N_MAX];
bool vizitat[N_MAX];
int N, M;
void citire()
{
int x, y;
fin>>N;
fin>>M;
for(int i=0; i<M; i++)
{
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[0]++;
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;
}