Pagini recente » Cod sursa (job #2492121) | Cod sursa (job #192966) | Cod sursa (job #1288356) | Cod sursa (job #2523505) | Cod sursa (job #669607)
Cod sursa(job #669607)
// 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,answer;
int indexx[MAXSIZE];
int lowLink[MAXSIZE];
bool inStack[MAXSIZE];
vector<int> graph[MAXSIZE];
stack<int> nodesStack;
vector< vector<int> > components;
void tarjan(int node);
int main()
{
in >> nodes >> edges;
int from,to;
for(int i=1;i<=edges;i++)
{
in >> from >> to;
graph[from].push_back(to);
}
for(int i=1;i<=nodes;i++)
if(!indexx[i])
tarjan(i);
out << answer << "\n";
vector< vector<int> >::iterator end = components.end();
vector<int>::iterator endC;
for(vector< vector<int> >::iterator it=components.begin();it!=end;++it)
{
endC = it->end();
for(vector<int>::iterator node=it->begin();node!=endC;++node)
out << *node << " ";
out << "\n";
}
return (0);
}
void tarjan(int currentNode)
{
indexx[currentNode] = lowLink[currentNode] = ++nodeCount;
inStack[currentNode] = true;
nodesStack.push(currentNode);
vector<int>::iterator end = graph[currentNode].end();
for(vector<int>::iterator 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])
{
answer++;
int node = 0;
vector<int> currentComponent;
while(node != currentNode)
{
node = nodesStack.top();
currentComponent.push_back(node);
inStack[node] = false;
nodesStack.pop();
}
components.push_back(currentComponent);
}
}