Pagini recente » Cod sursa (job #2022809) | Cod sursa (job #2444564) | Cod sursa (job #1084840) | Cod sursa (job #1603617) | Cod sursa (job #2683048)
///experiment cu nodurile in preordine
///este suficient sa luam n=2, m=1 si arcul(2,1)
#include <bits/stdc++.h>
using namespace std;
#define NM 100005
int n,m,postord[NM], t, viz[NM], k;
vector<int> G[NM], GT[NM], ctc[NM];
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void DFS(int x)
{
int i, w;
viz[x] = 1;
for (i = 0;i< G[x].size();i++)
{
w=G[x][i];
if (!viz[w])
DFS(w);
}
t++;
postord[t] = x;
}
void DFST(int x)
{
int i, w;
viz[x] = 1;
ctc[k].push_back(x);
for (i = 0;i<GT[x].size(); i++)
{
w=GT[x][i];
if (!viz[w])
DFST(w);
}
}
int main()
{
int i,j, x, y;
fin>>n>>m;
for (i=1;i<=m;i++)
{
fin>>x>>y;
G[x].push_back(y);///liste de adiacentaale grafului dat G
GT[y].push_back(x);///liste de adiacentaale grafului dat GT
}
///pasul 1
for (i = 1; i <= n; i++)
if (!viz[i])
DFS(i);
///resetam vectorul viz
for(i=1;i<=n;i++)
viz[i]=0;
k=0;
///parcurgem in in sens invers vectorul postord
for (i = n; i>=1; i--)
if (!viz[postord[i]])
{
k++;
DFST(postord[i]);
}
fout<<k<<'\n';
for (i = 1; i <= k; i++)
{
sort(ctc[i].begin(),ctc[i].end());
for (j=0; j < ctc[i].size(); j++)
fout<<ctc[i][j]<<' ';
fout<<'\n';
}
return 0;
}