Pagini recente » Cod sursa (job #156207) | Cod sursa (job #2489661) | Cod sursa (job #352995) | Cod sursa (job #1429807) | Cod sursa (job #3277509)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
typedef long long ll;
const ll Nmax=1e5+5, inf=1e9+5;
using pll=pair<ll, ll>;
int n, m, nrtc, crt;
int ord[Nmax];
bool vis[Nmax];
vector <int> ad[Nmax], adc[Nmax], tc[Nmax];
void dfs1 (int nod){
vis[nod]=1;
for (auto it:ad[nod])
if (!vis[it])
dfs1(it);
ord[crt++]=nod;
}
void dfs2 (int nod){
vis[nod]=1;
tc[nrtc].pb(nod+1);
for (auto it:adc[nod])
if (!vis[it])
dfs2(it);
}
inline void Kosaraju(){
for (int i=0; i<n; i++)
if (!vis[i])
dfs1(i);
for (int i=0; i<n; i++)
vis[i]=0;
for (int i=n-1; i>=0; i--)
if (!vis[ord[i]]){
dfs2(ord[i]);
nrtc++;
}
}
inline void Afisare(){
fout<<nrtc<<'\n';
for (int i=0; i<nrtc; i++){
for (auto it:tc[i])
fout<<it<<' ';
fout<<'\n';
}
}
int main()
{
fin>>n>>m;
int a, b;
for (int i=0; i<m; i++){
fin>>a>>b;
a--; b--;
ad[a].pb(b);
adc[b].pb(a);
}
Kosaraju();
Afisare();
return 0;
}