Pagini recente » Cod sursa (job #754886) | Cod sursa (job #75506) | Cod sursa (job #544328) | Cod sursa (job #1643893) | Cod sursa (job #1125310)
// Include
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
// Definitii
#define pb push_back
// Constante
const int sz = (int)1e5+1;
// Functii
void dfs(int node);
void reverseDfs(int node);
// Variabile
ifstream in("ctc.in");
ofstream out("ctc.out");
int nodes, edges;
int visited[sz];
vector<int> graph[sz], reverseGraph[sz]; // Graful si graful transpus
stack<int> nodesStack; // Stiva in care voi retine nodurile in ordinea
vector<int> answer;
vector< vector<int> > answers;
// Main
int main()
{
in >> nodes >> edges;
int rFrom, rTo;
while(edges--)
{
in >> rFrom >> rTo;
graph[rFrom].pb(rTo);
reverseGraph[rTo].pb(rFrom);
}
// Parcurge in adancime toate nodurile
for(int i=1 ; i<=nodes ; ++i)
dfs(i);
// Voi considera ca nodurile vizitate sunt in stiva, iar cele nevizitate nu.
// In acest mod, cand voi scoate un nod din stiva, il voi marca nevizitat (1)
// Cat timp mai am elemente in stiva
while(!nodesStack.empty())
{
// Iau valoarea nodului din varful stivei, ulterior stergandu-l
int node = nodesStack.top();
nodesStack.pop();
// Fac o parcurgere in adancime din nodul curent pe graful transpus
reverseDfs(node);
if(answer.size())
{
answers.pb(answer);
answer.clear();
}
}
out << answers.size() << '\n';
vector< vector<int> >::iterator it, end=answers.end();
for(it=answers.begin() ; it!=end ; ++it)
{
vector<int>::iterator vit, vend=it->end();
for(vit=it->begin() ; vit!=vend ; ++vit)
out << *vit << ' ';
out << '\n';
}
in.close();
out.close();
return 0;
}
void dfs(int node)
{
// Nu voi intra intr-un nod deja vizitat
if(visited[node])
return;
// Marchez nodul ca vizitat
visited[node] = true;
// Iau toti vecinii nodului curent
vector<int>::iterator it, end=graph[node].end();
// Continui parcurgerea in adancime din fiecare vecin al nodului curent
for(it=graph[node].begin() ; it!=end ; ++it)
dfs(*it);
// La intoarcerea din recursivitate (cand toti vecinii nodului curent sunt deja vizitati),
// introduc nodul curent in stiva
nodesStack.push(node);
}
void reverseDfs(int node)
{
// Nu voi intra intr-un nod deja vizitat
if(!visited[node])
return;
// Marchez nodul ca nevizitat - vezi (1)
visited[node] = false;
// Iau toti vecinii nodului curent
vector<int>::iterator it, end=reverseGraph[node].end();
// Continui parcurgerea in adancime din fiecare vecin al nodului curent
for(it=reverseGraph[node].begin() ; it!=end ; ++it)
reverseDfs(*it);
// Fiecare parcurgere va determina cate o componenta tare conexa
answer.pb(node);
}