Pagini recente » Cod sursa (job #2390439) | Cod sursa (job #2132313) | Cod sursa (job #1994387) | Cod sursa (job #1896956) | Cod sursa (job #2798178)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define Nmax 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
// aici folosesc un singur vector de noduri vizitate, pe care il reinitializez cu 0 dupa parcurgerea DFS pe graful normal, adica inainte de parcurgerea DFS pe graful transpus
int n, m, nrCTC, visited[Nmax];
vector<int> la[Nmax], grafTranspus[Nmax], sol[Nmax]; // folosim graful transpus doarece ne intereseaza sa putem ajunge din orice nod
// al componentei conexe in oricare altul tot al sau => verificam asa accesibilitatea
stack<int> S; // pe baza ideii de la DFS; imbunatatirea alg. plus minus
void dfsG(int x)
{
visited[x] = 1;
for (int i = 0; i < la[x].size(); ++i)
if (!visited[la[x][i]]) { // marcam in viz1 nodurile vizitate de dfs aplicat pe graful normal (in semn de plus)
//cout << "->dfsG(" << la[x][i] << ")\n";
dfsG(la[x][i]);
//cout << "Back to " << x << endl;
}
//cout << "Push " << x << endl;
S.push(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);
visited[x] = 1;
for (int i = 0; i < grafTranspus[x].size(); ++i)
if (!visited[grafTranspus[x][i]]) // 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(grafTranspus[x][i]);
// cout << "Back to " << x << endl;
}
}
void Kosaraju()
{
for (int i=1; i<=n; i++)
if (!visited[i]) {
//cout << "->dfsG(" << i << ")\n";
dfsG(i);
}
for (int i=1; i<=n; i++) {
visited[i] = false; // clear-ul vectorului pt a-l refolosi la urm dfs
}
// cout << "Stiva in ordinea inversa intrarii:\n";
while (!S.empty())
{
int v = S.top();
// cout << v << " ";
S.pop();
if (!visited[v]) {
// cout << "->dfsGT(" << v << ")\n";
dfsGT(v);
// cout << "Back to " << v << " where nrCTC = ";
nrCTC++;
// cout << nrCTC << endl;
}
}
}
int main() {
int x, y;
fin >> n >> m;
for (int i=0; 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);
}
Kosaraju();
fout << nrCTC << endl;
for(int i = 0; i < nrCTC; ++i) {
for(int j = 0; j < sol[i].size(); ++j)
fout << sol[i][j] << " ";
if (i!=nrCTC-1)
fout << endl;
}
return 0;
}