Pagini recente » Cod sursa (job #241049) | Cod sursa (job #2645117) | Cod sursa (job #2462933) | Cod sursa (job #1312925) | Cod sursa (job #3263896)
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#define VMAX 100005
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
vector<int> graf[VMAX];
vector<int> graf_invers[VMAX];
bool vizitat[VMAX];
int timp=0,nrc=0;
int postordine[VMAX];
vector<int> ctc[VMAX];
void dfs(int nod)
{
vizitat[nod]=1;
for(auto it:graf[nod])
{
if(vizitat[it]==0)
dfs(it);
}
postordine[timp++]=nod;
}
void dfs_pe_inv(int nod)
{
vizitat[nod]=0;
ctc[nrc].push_back(nod);
for(auto it:graf_invers[nod])
{
if(vizitat[it])
{
dfs_pe_inv(it);
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
int n,m,i,j,k,t,q,nr,minim,maxim,suma;
fin>>n>>m;
for(i=0;i<m;i++)
{
fin>>j>>k;
graf[j].push_back(k);
graf_invers[k].push_back(j);
}
for(i=1;i<=n;i++)
{
if(vizitat[i]==0)
dfs(i);
}
for(i=n;i>=0;i--)
{
if(vizitat[postordine[i]]!=0)
{
nrc++;
dfs_pe_inv(postordine[i]);
}
}
fout<<nrc<<'\n';
for(i=1;i<=nrc;i++)
{
for(j=0;j<ctc[i].size();j++)
fout<<ctc[i][j]<<' ';
fout<<'\n';
}
return 0;
}