Pagini recente » Cod sursa (job #1424956) | Cod sursa (job #2978104)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
ifstream f("ctc.in");
ofstream g("ctc.out");
const int N = 1e5 + 5;
int n, k, used, u[N];
vector<int> G[N], GT[N], ctc[N];
stack<int> s;
void read(), dfs(int), dfsGT(int);
int main()
{
read();
for (int i = 1; i <= n; i++)
if (!u[i]) dfs(i);
memset(u, 0, sizeof u);
while (used != n){
while (u[s.top()]) s.pop();
k++; dfsGT(s.top());
s.pop();
}
g << k << '\n';
for (int i = 1; i <= k; i++){
for (auto it: ctc[i]) g << it << ' ';
g << '\n';
}
return 0;
}
void read(){
int m, a, b;
f >> n >> m;
for (; m; m--){
f >> a >> b;
G[a].pb(b); GT[b].pb(a);
}
}
void dfs(int nod){
u[nod] = 1;
for (auto it: G[nod])
if (!u[it])
dfs(it);
s.push(nod);
}
void dfsGT(int nod){
u[nod] = 1; used++;
ctc[k].pb(nod);
for (auto it: GT[nod])
if (!u[it])
dfsGT(it);
}