Pagini recente » Cod sursa (job #1361334) | Cod sursa (job #3146250) | Cod sursa (job #2715891) | Cod sursa (job #2717303) | Cod sursa (job #797627)
Cod sursa(job #797627)
#include <fstream>
#include <vector>
#include <algorithm>
#define DIM 100010
using namespace std;
vector <int> L[DIM];
vector <int> P[DIM];
int viz[DIM];
int low[DIM];
int stack[DIM];
int N, M, i, j, x, y, s, next, ctc;
void dfs(int x) {
next++;
viz[x] = next;
low[x] = next;
stack[++s] = x;
int i, sz;
for (i=0, sz = L[x].size(); i<sz; i++) {
if (!viz[L[x][i]]) {
dfs(L[x][i]);
low[x] = min(low[x], low[L[x][i]]);
} else
if (viz[L[x][i]] > 0)
low[x] = min(low[x], low[L[x][i]]);
}
if (low[x] == viz[x]) {
int v;
ctc++;
do {
v = stack[s--];
viz[v] = - viz[v];
P[ctc].push_back(v);
} while (v!=x);
}
}
int main() {
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>N>>M;
for (i=1;i<=M;i++) {
f>>x>>y;
L[x].push_back(y);
}
for (i=1;i<=N;i++)
if (viz[i] == 0) {
dfs(i);
}
g<<ctc<<"\n";
for (i=1;i<=ctc;i++) {
for (j=0;j<P[i].size();j++)
g<<P[i][j]<<" ";
g<<"\n";
}
f.close();
g.close();
return 0;
}