Pagini recente » Cod sursa (job #1608169) | Cod sursa (job #94884) | Cod sursa (job #2125992) | Cod sursa (job #1668268) | Cod sursa (job #507743)
Cod sursa(job #507743)
// http://infoarena.ro/problema/ctc
#include <fstream>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>
using namespace std;
int nodes,edges,counter,stronglyConnectedComponents;
vector< list<int> > graph;
stack<int> nodeStack;
vector<bool> inStack;
vector<int> indexx,lowlink,oneSolution;
vector< vector<int> > solution;
void read();
void tarjan(int toVisit);
void write();
int main() {
read();
for(int i=1;i<=nodes;i++)
if(!indexx.at(i)) // daca nu a fost vizitat
tarjan(i);
write();
return (0);
}
void read() {
ifstream in("ctc.in");
int from,to;
in >> nodes >> edges;
graph.resize(nodes+1);
inStack.resize(nodes+1);
indexx.resize(nodes+1);
lowlink.resize(nodes+1);
for(int i=1;i<=edges;i++) {
in >> from >> to;
graph.at(from).push_back(to);
}
in.close();
}
void tarjan(int toVisit) {
indexx.at(toVisit) = ++counter;
lowlink.at(toVisit) = counter;
nodeStack.push(toVisit); // adaug in stiva nodul curent
inStack.at(toVisit) = true; // il marchez ca fiind in stiva
for(list<int>::iterator it=graph.at(toVisit).begin();it!=graph.at(toVisit).end();it++)
if(!indexx.at(*it)) { // daca nu a fost vizitat
tarjan(*it);
lowlink.at(toVisit) = min(lowlink.at(toVisit),lowlink.at(*it));
}
else
if(inStack.at(*it))
lowlink.at(toVisit) = min(lowlink.at(toVisit),lowlink.at(*it));
// daca s-a identificat o componenta tare conexa
if(lowlink.at(toVisit) == indexx.at(toVisit)) {
int node = NULL;
oneSolution.clear(); // se goleste vectorul
while(node != toVisit) {
node = nodeStack.top();
nodeStack.pop(); // se scoate nodul din stiva
inStack.at(node) = false;
oneSolution.push_back(node);
}
solution.push_back(oneSolution); // se adauga solutia
stronglyConnectedComponents++; // creste numarul componentelor tare conexe
}
}
void write() {
ofstream out("ctc.out");
int end;
out << stronglyConnectedComponents << "\n";
for(int i=0;i<stronglyConnectedComponents;i++) {
end = solution.at(i).size();
for(int k=0;k<end;k++)
out << solution.at(i).at(k) << " ";
out << "\n"; // cu endl nu intra in timp :)
}
out.close();
}