Pagini recente » Cod sursa (job #1636890) | Cod sursa (job #561164) | Cod sursa (job #1585259) | Cod sursa (job #1576487) | Cod sursa (job #483065)
Cod sursa(job #483065)
//CTC
#include<cstdio>
#include<vector>
using namespace std;
const int N=100001;
int n, m, rep[N], poz, nrcc;
bool viz[N];
vector <int> g[N];
vector <int> rv[N];
vector <int> ctc[N];
void Read()
{
int a, b;
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d",&a,&b);
g[a].push_back(b);
rv[b].push_back(a);
}
}
void Sat(int i)
{
int sz=g[i].size();
viz[i]=1;
for( int j=0; j<sz; ++j)
if(!viz[g[i][j]])
Sat(g[i][j]);
rep[++poz]=i;
}
void Parc()
{
for( int i=1; i<=n; ++i)
if(!viz[i])
Sat(i);
}
void Rsat( int i, int cc)
{
int sz=rv[i].size();
viz[i]=0;
ctc[cc].push_back(i);
for( int j=0; j<sz; ++j)
if(viz[rv[i][j]])
Rsat( rv[i][j], cc);
}
void InvP()
{
for( int i=n; i>=1; --i)
if(viz[rep[i]])
Rsat( rep[i], ++nrcc);
}
void GetC()
{
int sz;
printf("%d\n",nrcc);
for( int i=1; i<=nrcc; ++i)
{
sz=ctc[i].size();
for( int j=0; j<sz; ++j)
printf("%d ",ctc[i][j]);
printf("\n");
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
Read();
Parc();
InvP();
GetC();
return 0;
}