Pagini recente » Cod sursa (job #994331) | Cod sursa (job #2050261) | Cod sursa (job #3130865) | Cod sursa (job #436624) | Cod sursa (job #505044)
Cod sursa(job #505044)
// 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))
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);
inStack.at(toVisit) = true;
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));
if(lowlink.at(toVisit) == indexx.at(toVisit)) {
int toPrint;
oneSolution.clear(); // se goleste vectorul
while(toPrint != toVisit) {
toPrint = nodeStack.top();
nodeStack.pop();
inStack.at(toPrint) = false;
oneSolution.push_back(toPrint);
}
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();
}