Pagini recente » Cod sursa (job #2049591) | Cod sursa (job #3148704) | Cod sursa (job #252614) | Cod sursa (job #1934120) | Cod sursa (job #1468778)
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> G[100002],co[100001];
int viz[100001], retLv[100002];
int nrComp, check,n,m, nod1, nod2;
stack<int> stiva;
void DFS(int nod,int level)
{
viz[nod] = check; retLv[nod] = level;
stiva.push(nod);
for(int i=0;i<G[nod].size();i++)
if(viz[G[nod][i]] == 0)
{
DFS(G[nod][i],level+1);
if(retLv[G[nod][i]] < retLv[nod])
retLv[nod] = retLv[G[nod][i]];
}
else
if(viz[G[nod][i]] == check)
{
if(retLv[G[nod][i]] < retLv[nod])
retLv[nod] = retLv[G[nod][i]];
}
if(retLv[nod] == level)
{
nrComp ++;
while(stiva.top() != nod)
{
co[nrComp].push_back(stiva.top());
stiva.pop();
}
co[nrComp].push_back(nod);
stiva.pop();
}
}
int main()
{
fin>>n>>m;
for(int i=1;i<=m;i++)
{
fin>>nod1>>nod2;
G[nod1].push_back(nod2);
}
for(int i=1;i<=n;i++)
if(viz[i]==0)
{
check++;
DFS(i,1);
}
fout<<nrComp<<'\n';
for(int i=1;i<=nrComp;i++)
{
sort(co[i].begin(),co[i].end());
for(int j=0;j<co[i].size();j++)
fout<<co[i][j]<<' ';
fout<<'\n';
}
return 0;
}