Pagini recente » Cod sursa (job #1026015) | Cod sursa (job #511257) | Cod sursa (job #2920679) | Cod sursa (job #2896949) | Cod sursa (job #1635629)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, nrc;
vector<vector<int>> G1, G2;
vector<bool> s, s1;
stack<int> stk;
vector<int> c;
vector<vector<int>> cc;
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 (!stk.empty()) {
x = stk.top(); stk.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;
stk.push(x);
for (const auto & e : G1[x])
if (!s[e]) DF(e);
}
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);
for (int i = 0, x, y; i < m; i++) {
fin >> x >> y;
G1[x].push_back(y);
G2[y].push_back(x);
}
}