Pagini recente » Cod sursa (job #975364) | Cod sursa (job #701606) | tema | Cod sursa (job #975290) | Cod sursa (job #1820292)
#include <bits/stdc++.h>
using namespace std;
const int SPQR = 1e5 + 5;
vector<vector<int>> ctc;
bitset<SPQR> instk, gws;
vector<int> stk;
vector<int> g[SPQR];
int low[SPQR], lvl[SPQR];
void dfs(int nod) {
static int now = 0;
instk[nod] = true;
gws[nod] = true;
stk.push_back(nod);
low[nod] = lvl[nod] = ++now;
for (auto i: g[nod]) {
if (!gws[i])
dfs(i);
if (instk[i])
low[nod] = min(low[nod], low[i]); }
if (low[nod] == lvl[nod]) {
int tmp;
ctc.push_back(vector<int>(0));
do {
tmp = stk.back();
stk.pop_back(), instk[tmp] = false;
ctc.back().push_back(tmp); }
while (tmp != nod); } }
int main(void) {
ifstream fi("ctc.in");
ofstream fo("ctc.out");
int n, m, u, v;
fi >> n >> m;
for (int i = 1; i <= m; ++i) {
fi >> u >> v;
g[u].push_back(v); }
for (int i = 1; i <= n; ++i)
if (!gws[i])
dfs(i);
fo << ctc.size() << '\n';
for (auto &i: ctc) {
for (auto j: i)
fo << j << ' ';
fo << '\n'; }
return 0; }