Pagini recente » Cod sursa (job #1649759) | Cod sursa (job #1292751) | Cod sursa (job #1837315) | Cod sursa (job #462259) | Cod sursa (job #527631)
Cod sursa(job #527631)
// http://infoarena.ro/problema/ctc
#include <fstream>
#include <algorithm>
#include <list>
#include <stack>
using namespace std;
#define maxSize 100001
int nodes,counter,stronglyConnectedComponents;
int indexx[maxSize],lowLink[maxSize];
bool inStack[maxSize];
list<int> graph[maxSize];
list< list<int> > solution;
stack<int> myStack;
void read();
void tarjan(int currentNode);
void write();
int main() {
read();
for(int i=1;i<=nodes;i++)
if(!indexx[i]) // daca nu a fost vizitat
tarjan(i);
write();
return (0);
}
void read() {
ifstream in("ctc.in");
int edges,from,to;
in >> nodes >> edges;
for(int i=1;i<=edges;i++) {
in >> from >> to;
graph[from].push_back(to);
}
in.close();
}
void tarjan(int currentNode) {
indexx[currentNode] = ++counter;
lowLink[currentNode] = counter;
myStack.push(currentNode); // se adauga in stiva nodul curent
inStack[currentNode] = true; // se marcheza ca fiind in stiva
list<int>::iterator neighbour;
for(neighbour=graph[currentNode].begin();neighbour!=graph[currentNode].end();neighbour++)
if(!indexx[*neighbour]) { // daca nu a fost vizitat
tarjan(*neighbour);
lowLink[currentNode] = min(lowLink[currentNode],lowLink[*neighbour]);
}
else
if(inStack[*neighbour])
lowLink[currentNode] = min(lowLink[currentNode],lowLink[*neighbour]);
// daca s-a identificat o componenta tare-conexa
if(lowLink[currentNode] == indexx[currentNode]) {
int node = NULL;
list<int> currentSolution;
while(node != currentNode) {
node = myStack.top(); // se extrage nodul din varful stivei
myStack.pop(); // se elimina nodul extras
inStack[node] = false;
currentSolution.push_back(node); // se adauga in solutia curenta
}
solution.push_back(currentSolution); // se adauga solutia
stronglyConnectedComponents++; // creste numarul componentelor tare-conexe
}
}
void write() {
ofstream out("ctc.out");
list< list<int> >::iterator first;
list<int>::iterator second;
out << stronglyConnectedComponents << "\n";
for(first=solution.begin();first!=solution.end();first++) {
for(second=first->begin();second!=first->end();second++)
out << *second << " ";
out << "\n";
}
}