Pagini recente » Cod sursa (job #625565) | Cod sursa (job #68026) | Cod sursa (job #1578441) | Cod sursa (job #67047) | Cod sursa (job #640639)
Cod sursa(job #640639)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
int f[100001], s[200001], t, n, m;
bool viz[100001];
//fstream fi("dffinal2.in",ios::in);
ifstream fi("ctc.in");
ofstream fo("ctc.out");
vector <int> v[100001], vt[100001];
// In s retinem nodurile sortate dupa timpii finali.
void dffinal(int i) { //fo << "i = " << i << endl;
int c;
viz[i] = true; t++; // fo << t << endl;
for (c = 0; c < v[i].size(); c++)
if (!viz[v[i][c]]) // Nu a fost vizitat.
dffinal(v[i][c]);
t++; f[i] = t; s[t] = i; // fo << "f[" << i << "] = " << t << endl;
}
bool pr;
void dfsc(int i) {
int c;
if(pr)
fo << i << ' ';
viz[i] = true; // Il consideram vizitat.
for (c = 0; c < vt[i].size(); c++)
if (!viz[vt[i][c]]) // nu a fost vizitat.
dfsc(vt[i][c]); // parcurgem in adancime.
}
int main() {
int x, y, i, nc, l, c;
fi >> n >> m;
for (i = 1; i <= m; i++) {
fi >> x >> y;
v[x].push_back (y);
vt[y].push_back (x);
}
t = 0;
for(i = 1;i<=n;i++)
if(!viz[i])
dffinal(i);
memset(viz, 0, 100001);
int com=0;
for(l = t;l>=0;l--)
if(s[l])
{
nc = s[l];
if(!viz[nc])
{
com++;
dfsc(nc);
}
}
fo<<com<<'\n';
memset(viz, 0, 100001);
pr = true;
for (l = t; l >= 0; l--) { // Parcurgem sirul sortat al nodurilor.
if (s[l]) { // S-ar putea ca locului l sa nu ii corespunda un nod.
nc = s[l]; // nodul curent
if (!viz[nc]) { // Nu a fost vizitat.
dfsc(nc); // Parcurgem o componenta.
fo << '\n';
}
}
}
return 0;
}