Pagini recente » Cod sursa (job #621008) | Cod sursa (job #3206214) | Cod sursa (job #126794) | Cod sursa (job #3264821) | Cod sursa (job #2786605)
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
#define cin f
#define cout g
//#define int long long
const int Max = 1e5 + 1;
void nos()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
vector < int > v[Max];
vector < int > vt[Max];
int n,m;
void read()
{
f>>n>>m;
int i;
for(i=1;i<=m;i++)
{
int n1,n2;
f>>n1>>n2;
v[n1].push_back(n2);
vt[n2].push_back(n1);
}
}
vector < int > ordine;
int viz[Max];
void dfs(int nod)
{
if(viz[nod] == 0)
{
viz[nod] = 1;
for(auto vec : v[nod])
dfs(vec);
ordine.push_back(nod);
}
}
int compo[Max];
void baga(int who, int where)
{
if(compo[who] == 0)
{
compo[who] = where;
for(auto vec : vt[who])
baga(vec,where);
}
}
int current_comp_id;
void ctc()
{
int i;
current_comp_id = 0;
for(auto candidat : ordine)
{
if(compo[candidat] == 0)
{
++current_comp_id;
baga(candidat,current_comp_id);
}
}
}
void compute_CTC()
{
int i;
for(i=1;i<=n;i++)
if(viz[i] == 0)
dfs(i);
reverse(ordine.begin(),ordine.end());
ctc();
}
vector < vector < int > > componente;
void solve()
{
compute_CTC();
componente.resize(current_comp_id + 1);
int i;
for(i=1;i<=n;i++)
componente[compo[i]].push_back(i);
cout<<current_comp_id<<'\n';
for(i=1;i<=current_comp_id;i++)
{
for(auto nod : componente[i])
cout<<nod<<' ';
cout<<'\n';
}
}
void restart()
{
}
int32_t main()
{
nos();
read();
solve();
restart();
return 0;
}