Pagini recente » Cod sursa (job #550575) | Cod sursa (job #307658) | Cod sursa (job #484177) | Cod sursa (job #540684) | Cod sursa (job #1655011)
#include <fstream>
#include <vector>
using namespace std;
vector <int> adia[100010];
vector <int> adiaback[100010];
vector <int> sortop;
vector <int> componente[100010];
int c = 0;
bool viz[100010];
bool vizback[100010];
int n, m;
void bkt(int nod);
void bktback(int nod, int nr);
int main()
{
ifstream in("ctc.in");
in >> n >> m;
int a, b;
for (int i = 0; i < m; i++) {
in >> a >> b;
adia[a].push_back(b);
adiaback[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
if ( !viz[i] ) {
bkt(i);
}
} /// sortare topologica
for (int i = sortop.size() - 1; i >= 0; i--) {
if ( vizback[sortop[i]] )
continue;
bktback(sortop[i], c);
c++;
}
ofstream out("ctc.out");
out << c;
for (int i = 0; i < c; i++) {
out << '\n';
for (auto j : componente[i]) {
out << j << ' ';
}
}
return 0;
}
void bktback(int nod, int nr) {
vizback[nod] = 1;
componente[nr].push_back(nod);
for (auto i : adiaback[nod]) {
if ( !vizback[i] ) {
bktback(i, nr);
}
}
}
void bkt(int nod) {
viz[nod] = 1;
for (auto i : adia[nod]) {
if ( !viz[i] )
bkt(i);
}
sortop.push_back(nod);
}