Pagini recente » Cod sursa (job #1885502) | Cod sursa (job #1708520) | Cod sursa (job #330438) | Cod sursa (job #2464087) | Cod sursa (job #724066)
Cod sursa(job #724066)
// http://infoarena.ro/problema/ctc
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int MAXSIZE = 100001;
ifstream in("ctc.in");
ofstream out("ctc.out");
int nodes,edges,nodeCount;
bool inStack[MAXSIZE];
int indexx[MAXSIZE],lowLink[MAXSIZE];
stack<int> nodesStack;
vector<int> graph[MAXSIZE];
vector< vector<int> > components;
void tarjan(int currentNode);
int main() {
in >> nodes >> edges;
int from,to;
for(int i=1;i<=edges;i++) {
in >> from >> to;
graph[from].push_back(to);
}
in.close();
for(int i=1;i<=nodes;i++)
if(!indexx[i])
tarjan(i);
out << components.size() << "\n";
for(unsigned int i=0;i<components.size();i++) {
for(unsigned int k=0;k<components[i].size();k++)
out << components[i][k] << " ";
out << "\n";
}
out.close();
return (0);
}
void tarjan(int currentNode) {
indexx[currentNode] = lowLink[currentNode] = ++nodeCount;
inStack[currentNode] = true;
nodesStack.push(currentNode);
vector<int>::iterator it,end = graph[currentNode].end();
for(it=graph[currentNode].begin();it!=end;++it)
if(!indexx[*it]) {
tarjan(*it);
lowLink[currentNode] = min(lowLink[currentNode],lowLink[*it]);
}
else
if(inStack[*it])
lowLink[currentNode] = min(lowLink[currentNode],indexx[*it]);
if(indexx[currentNode] == lowLink[currentNode]) {
int node = 0;
vector<int> currentComponent;
while(node != currentNode) {
node = nodesStack.top();
nodesStack.pop();
inStack[node] = false;
currentComponent.push_back(node);
}
components.push_back(currentComponent);
}
}