Pagini recente » Cod sursa (job #2707827) | Cod sursa (job #1429892) | Cod sursa (job #840859) | Cod sursa (job #1101010) | Cod sursa (job #1261921)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n,m,i,j,x,y,nod,nr,nr_comp;
int d[100001],ordine[100001];
bool fol[100001];
vector<int> graf[100001],graft[100001],rasp[100001];
void bfs(int nod)
{
for(int i=0; i<graf[nod].size(); i++)
{
if(!fol[graf[nod][i]])
{
fol[graf[nod][i]]=1;
d[graf[nod][i]]=nr-1; nr--;
bfs(graf[nod][i]);
}
}
}
void bfs_t(int nod)
{
for(int i=0; i<graft[nod].size(); i++)
{
if(!fol[graft[nod][i]])
{
fol[graft[nod][i]]=1;
rasp[nr_comp].push_back(graft[nod][i]);
bfs_t(graft[nod][i]);
}
}
}
int main()
{
cin>>n>>m;
for(i=1; i<=m; i++)
{
cin>>x>>y;
graf[x].push_back(y); // graful normal
graft[y].push_back(x); // graful transpus
}
d[1]=n; fol[1]=1; nr=n;
bfs(1); // fac bfs si atrbui in d[i] timpul la care a fost prelucrat nodu i ( ordine descrescatoare )
for(i=1; i<=n; i++) // sortez nodurile in ordine descrescatoare
ordine[n-d[i]+1]=i;
nr_comp=0;
for(i=1; i<=n; i++)
fol[i]=0;
for(i=1; i<=n; i++)
{
if(!fol[ordine[i]])
{
fol[ordine[i]]=1;
rasp[++nr_comp].push_back(ordine[i]);
bfs_t(ordine[i]);
}
}
/*for(i=1; i<=n; i++)
cout<<ordine[i]<<" ";
cout<<"\n\n";*/
cout<<nr_comp<<"\n";
for(i=1; i<=nr_comp; i++)
{
for(j=0; j<rasp[i].size(); j++)
cout<<rasp[i][j]<<" ";
cout<<"\n";
}
}