Pagini recente » Cod sursa (job #372357) | Cod sursa (job #1623579) | Cod sursa (job #2047707) | Cod sursa (job #2890990) | Cod sursa (job #2832255)
#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
// aici folosesc 2 vectori de noduri vizitate, unul pt graful normal, unul pt graful transpus (in ideea alg. plus minus)
int n, m, nrCTC, viz1[Nmax], viz2[Nmax];
vector<int> la[Nmax], grafTranspus[Nmax], sol[Nmax], S; // folosim graful transpus doarece ne intereseaza sa putem ajunge din orice nod
// al componentei conexe in oricare altul tot al sau => verificam asa accesibilitatea
void dfsG(int x)
{
viz1[x] = 1;
for (auto vecin: la[x])
if (!viz1[vecin]) { // marcam in viz1 nodurile vizitate de dfs aplicat pe graful normal (in semn de plus)
//cout << "->dfsG(" << la[x][i] << ")\n";
dfsG(vecin);
//cout << "Back to " << x << endl;
}
//cout << "Push " << x << endl;
S.push_back(x); // ca sa pastreze ordinea de finalizare a nodurilor => parcurg GT in ordinea in care le scot de pe stiva
}
void dfsGT(int x) // aplicam dfs si pe graful transpus
{
//cout << "sol[" << nrCTC << "].push_back( " << x << ");\n";
sol[nrCTC].push_back(x);
viz2[x] = 1;
for (auto vecin: grafTranspus[x])
if (!viz2[vecin]) // daca sunt marcate inseamna ca nu fac parte din aceasta CTC sau le-am viz deja pt CTC curenta
{
//cout << "->dfsGT(" << grafTranspus[x][i] << ")\n";
dfsGT(vecin);
//cout << "Back to " << x << endl;
}
}
int main() {
int x, y;
fin >> n >> m;
for (int i=1; i<=m; i++) { // obs: in la[x], nodurile adiacente cu x nu se pun in ordine crescatoare, ci in ordinea citirii
fin >> x >> y;
la[x].push_back(y); // graf orientat
grafTranspus[y].push_back(x); // muchia inversa
}
//Kosaraju();
for (int i=1; i<=n; i++) {
if (!viz1[i]) {
//cout << "->dfsG(" << i << ")\n";
dfsG(i);
}
}
reverse(S.begin(), S.end());
for (auto i: S) {
if (!viz2[i]) {
//cout << "->dfsG(" << i << ")\n";
nrCTC ++;
dfsGT(i);
}
}
fout << nrCTC << endl;
for(int i = 1; i <= nrCTC; ++i) {
for(auto j: sol[i])
fout << j << " ";
fout << endl;
}
return 0;
}