Pagini recente » Cod sursa (job #1707469) | Cod sursa (job #1445440) | Cod sursa (job #572326) | Cod sursa (job #577454) | Cod sursa (job #3168497)
#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;
bitset<N> u;
stack<int> stk;
vector<vector<int>> G, GT, CTC;
void read(), dfsG(int), dfsGT(int);
int main()
{
read();
for (int i = 1; i <= n; i++)
if (!u[i]) dfsG(i);
u.reset();
while (!stk.empty()){
int nod = stk.top(); stk.pop();
if (!u[nod]) {
CTC.pb({});
dfsGT(nod), k++;
}
}
g << k << '\n';
for (int i = 0; i < k; i++){
for (auto v: CTC[i]) g << v << ' ';
g << '\n';
}
return 0;
}
void read(){
int m; f >> n >> m;
G.resize(n+3); GT.resize(n+3);
while (m--){
int a, b; f >> a >> b;
G[a].pb(b); GT[b].pb(a);
}
}
void dfsG(int nod){
u[nod] = 1;
for (auto v: G[nod])
if(!u[v]) dfsG(v);
stk.push(nod);
}
void dfsGT(int nod){
u[nod] = 1; CTC[k].pb(nod);
for (auto v: GT[nod])
if (!u[v]) dfsGT(v);
}