Pagini recente » Cod sursa (job #3267887) | Cod sursa (job #2876788) | Cod sursa (job #2102254) | Cod sursa (job #2569213) | Cod sursa (job #3214216)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NMax = 1e5 + 5;
vector<int>G[NMax], GT[NMax], CTC[NMax];
stack<int>S;
int n,NrCtc,beenThere[NMax];
void read();
void solve();
void DFSP(int nod);
void DFSM(int nod);
void print();
int main() {
read();
solve();
print();
fin.close();
fout.close();
return 0;
}
void read() {
int m, x, y;
fin >> n >> m;
for (int i = 1; i <= m; ++i) {
fin >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void solve() {
for (int i = 1; i <= n; ++i)
if (!beenThere[i])
DFSP(i);
while (!S.empty()) {
int nod = S.top();
S.pop();
if (beenThere[nod] == 1) {
NrCtc++;
DFSM(nod);
}
}
}
void DFSP(int nod) {
beenThere[nod] = 1;
for (auto& i : G[nod])
if (!beenThere[i])
DFSP(i);
S.push(nod);
}
void DFSM(int nod) {
beenThere[nod] = 2;
CTC[NrCtc].push_back(nod);
for (auto& i : GT[nod])
if (beenThere[i] == 1)
DFSM(i);
}
void print() {
fout << NrCtc << endl;
for (int i = 1; i <= NrCtc; ++i) {
for (auto& j : CTC[i])
fout << j << ' ';
fout << endl;
}
}