Pagini recente » Cod sursa (job #329363) | Cod sursa (job #1581023) | Cod sursa (job #1032855) | Cod sursa (job #215606) | Cod sursa (job #1165290)
#include <fstream>
#include <vector>
using namespace std;
const int MAX_N = 100002;
int N, M, nrSCC;
vector < int > v[MAX_N], w[MAX_N], SCC[MAX_N], a;
bool m[MAX_N];
void DFS1(int x) {
m[x] = 1;
for(int i = 0; i < (int) v[x].size(); ++i) {
int y = v[x][i];
if(!m[y])
DFS1(y);
}
a.push_back(x);
}
void DFS2(int x) {
m[x] = 1;
SCC[nrSCC].push_back(x);
for(int i = 0; i < (int) w[x].size(); ++i) {
int y = w[x][i];
if(!m[y])
DFS2(y);
}
}
int main() {
ifstream f("ctc.in");
ofstream g("ctc.out");
f >> N >> M;
for(int i = 1, x, y; i <= M; ++i) {
f >> x >> y;
v[x].push_back(y);
w[y].push_back(x);
}
for(int i = 1; i <= N; ++i)
if(!m[i])
DFS1(i);
for(int i = 1; i <= N; ++i)
m[i] = 0;
for(int i = a.size() - 1; i >= 0; --i)
if(!m[a[i]]) {
++nrSCC;
DFS2(a[i]);
}
g << nrSCC << "\n";
for(int i = 1; i <= nrSCC; ++i) {
for(int j = 0; j < (int) SCC[i].size(); ++j)
g << SCC[i][j] << " ";
g << "\n";
}
f.close();
g.close();
return 0;
}