Pagini recente » Cod sursa (job #887548) | Cod sursa (job #2738691) | Cod sursa (job #564812) | Cod sursa (job #1733855) | Cod sursa (job #1474050)
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
//#include <cstring>
#include <cmath>
#include <bitset>
#include <utility>
#include <stack>
#define MAXN 100005
using namespace std;
vector<int> v[MAXN], compConexa;
vector<vector<int> > final;
bool inStack[MAXN];
int index[MAXN], lowlink[MAXN], nrindex;
stack<int> S;
void tarjan(int n);
int main() {
int n, m, x, y, i, j;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
fin >> n >> m;
for (i = 0; i < m; ++i) {
fin >> x >> y;
v[x].push_back(y);
}
for (i = 1; i <= n; ++i) {
if (index[i] == 0)
tarjan(i);
}
fout << final.size() << '\n';
for (i = 0; i < final.size(); ++i) {
for (j = 0; j < final[i].size(); ++j)
fout << final[i][j] << ' ';
fout << '\n';
}
return 0;
}
void tarjan(int n) {
++nrindex;
index[n] = lowlink[n] = nrindex;
S.push(n);
inStack[n] = true;
vector<int>::iterator it;
for (it = v[n].begin(); it != v[n].end(); ++it) {
if (index[*it] == 0) {
tarjan(*it);
lowlink[n] = min(lowlink[n], lowlink[*it]);
}
else if (inStack[*it] == true)
lowlink[n] = min(lowlink[n], lowlink[*it]);
}
if (index[n] == lowlink[n]) {
compConexa.clear();
int node;
do {
node = S.top();
S.pop();
inStack[node] = 0;
compConexa.push_back(node);
} while (node != n);
final.push_back(compConexa);
}
}