Pagini recente » Cod sursa (job #1129385) | Cod sursa (job #1301378) | Cod sursa (job #1481732) | Cod sursa (job #1143301) | Cod sursa (job #536144)
Cod sursa(job #536144)
// http://infoarena.ro/problema/ctc
#include <fstream>
#include <vector>
#include <list>
#include <stack>
using namespace std;
#define maxSize 100001
int nodes,counter,stronglyConnectedComponents;
bool inStack[maxSize];
int indexx[maxSize];
int lowLink[maxSize];
vector<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])
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);
inStack[currentNode] = true;
vector<int>::iterator neighbour,end;
end = graph[currentNode].end();
for(neighbour=graph[currentNode].begin();neighbour!=end;++neighbour)
if(!indexx[*neighbour]) {
tarjan(*neighbour);
lowLink[currentNode] = min(lowLink[currentNode],lowLink[*neighbour]);
}
else
if(inStack[*neighbour])
lowLink[currentNode] = min(lowLink[currentNode],lowLink[*neighbour]);
if(lowLink[currentNode] == indexx[currentNode]) {
int node = 0;
list<int> currentSolution;
while(node != currentNode) {
node = myStack.top();
myStack.pop();
inStack[node] = false;
currentSolution.push_back(node);
}
solution.push_back(currentSolution);
stronglyConnectedComponents++;
}
}
void write() {
ofstream out("ctc.out");
list< list<int> >::iterator first,firstEnd;
list<int>::iterator second,secondEnd;
out << stronglyConnectedComponents << "\n";
firstEnd = solution.end();
for(first=solution.begin();first!=firstEnd;++first) {
secondEnd = first->end();
for(second=first->begin();second!=secondEnd;++second)
out << *second << " ";
out << "\n";
}
out.close();
}