Pagini recente » Cod sursa (job #2052439) | Cod sursa (job #567030) | Cod sursa (job #326845) | Cod sursa (job #1009476) | Cod sursa (job #3181153)
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
ifstream f("ctc.in");
ofstream g("ctc.out");
const int N = 1e5+3;
int n, k;
vector<vector<int>> G, GT, ctc;
bitset<N> u;
stack<int> stk;
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]) continue;
ctc.pb({}); dfsGT(nod);
k++;
}
g << k << '\n';
for (int i = 0; i < k; i++){
for (auto it: ctc[i]) g << it << ' ';
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);
}