Pagini recente » Cod sursa (job #2334359) | Utilizatori inregistrati la Infoarena Monthly 2014 - Runda 8 | Cod sursa (job #3130815) | Cod sursa (job #1049175) | Cod sursa (job #1650449)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M;
vector<vector<int>> G1, G2, CC;
vector<int> C;
vector<bool> s, s1;
stack<int> S;
int nrc;
void Read();
void DF(int x);
void DFt(int x);
void Write();
int main() {
Read();
for (int i = 1; i <= N; i++)
if (!s[i]) DF(i);
int x;
while (!S.empty()) {
x = S.top(); S.pop();
if (!s1[x]) {
nrc++;
C.clear();
DFt(x);
CC.push_back(C);
}
}
Write();
fin.close();
fout.close();
return 0;
}
void DFt(int x) {
s1[x] = true;
C.push_back(x);
for (const auto & e : G2[x]) {
if (!s1[e]) DFt(e);
}
}
void DF(int x) {
s[x] = true;
for (const auto e : G1[x])
if (!s[e]) DF(e);
S.push(x);
}
void Write() {
fout << nrc << '\n';
for (const auto & C : CC) {
for (const auto x : C)
fout << x << ' ';
fout << '\n';
}
}
void Read() {
fin >> N >> M;
G1 = G2 = vector<vector<int>>(N + 1);
s = s1 = vector<bool>(N + 1, false);
for (int i = 1, x, y; i <= M; i++) {
fin >> x >> y;
G1[x].push_back(y);
G2[y].push_back(x);
}
}