Pagini recente » Cod sursa (job #2781540) | Cod sursa (job #1602376) | Cod sursa (job #2071335) | Cod sursa (job #1917068) | Cod sursa (job #971015)
Cod sursa(job #971015)
#include <fstream>
#include <vector>
using namespace std;
const int MAX_N = 100002;
int N, M, Nr;
vector < int > v[MAX_N], w[MAX_N], comp[MAX_N], a;
bool m1[MAX_N], m2[MAX_N];
inline void DFS1(int x) {
m1[x] = 1;
for(size_t i = 0; i < v[x].size(); ++i)
if(!m1[v[x][i]])
DFS1(v[x][i]);
a.push_back(x);
}
inline void DFS2(int x) {
comp[Nr].push_back(x);
m2[x] = 1;
for(size_t i = 0; i < w[x].size(); ++i)
if(!m2[w[x][i]])
DFS2(w[x][i]);
}
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(!m1[i])
DFS1(i);
for(int i = a.size() - 1; i >= 0; --i)
if(!m2[a[i]])
++Nr, DFS2(a[i]);
g << Nr << '\n';
for(int i = 1; i <= Nr; ++i) {
for(size_t j = 0; j < comp[i].size(); ++j)
g << comp[i][j] << " ";
g << '\n';
}
f.close();
g.close();
return 0;
}