Pagini recente » Cod sursa (job #999291) | Cod sursa (job #2248036) | Cod sursa (job #3125902)
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100000
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n, m, nrCTC;
int ver[NMAX + 1];
vector <int> gf[NMAX + 1], gft[NMAX + 1], rsp[NMAX + 1];
stack <int> ord;
void dfsp(int nc) {
ver[nc] = 1;
for (int j = 0; j < gf[nc].size(); j++)
if (ver[gf[nc][j]] == 0)
dfsp(gf[nc][j]);
ord.push(nc);
}
void dfsm(int nc) {
ver[nc] = 2;
rsp[nrCTC].push_back(nc);
for (int j = 0; j < gft[nc].size(); j++)
if (ver[gft[nc][j]] == 1)
dfsm(gft[nc][j]);
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
gf[x].push_back(y);
gft[y].push_back(x);
}
for (int i = 1; i <= n; i++)
if (ver[i] == 0) {
dfsp(i);
}
while (!ord.empty()) {
int nc = ord.top();
if(ver[nc] == 1) {
nrCTC++;
dfsm(nc);
}
ord.pop();
}
fout << nrCTC << '\n';
for (int i = 1; i <= nrCTC; i++){
for (int j = 0; j < rsp[i].size(); j++)
fout << rsp[i][j] << ' ';
fout << '\n';
}
return 0;
}