Pagini recente » Cod sursa (job #1279043) | Cod sursa (job #2607844) | Cod sursa (job #1738284) | Cod sursa (job #1967531) | Cod sursa (job #1977025)
#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
struct graph
{
vector <int> v;
};
graph G[Nmax],GG[Nmax];
bitset <Nmax> viz;
int nr;
int pord[Nmax];
int ctc[Nmax];
void DFSG(int x)
{
int i;
viz[x]=true;
for(i=0;i<G[x].v.size();i++)
if(!viz[G[x].v[i]]) DFSG(G[x].v[i]);
pord[++nr]=x;
}
void DFSGG(int x)
{
int i;
ctc[x]=nr;
viz[x]=false;
for(i=0;i<GG[x].v.size();i++)
if(viz[GG[x].v[i]]) DFSGG(GG[x].v[i]);
}
int main()
{int n,m,k,i,j;
f>>n>>m;
for(k=1;k<=m;k++)
{
f>>i>>j;
G[i].v.push_back(j);
GG[j].v.push_back(i);
}
for(i=1;i<=n;i++)
if(!viz[i]) DFSG(i);
nr=0;
for(i=n;i>0;i--)
if(viz[pord[i]])
{
nr++;
DFSGG(pord[i]);
}
g<<nr<<'\n';
for(i=1;i<=nr;i++)
{
for(j=1;j<=n;j++)
if(ctc[j]==i) g<<j<<' ';
g<<'\n';
}
return 0;
}