Pagini recente » Cod sursa (job #1579807) | Cod sursa (job #590113) | Cod sursa (job #3183164) | Cod sursa (job #11601) | Cod sursa (job #735836)
Cod sursa(job #735836)
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define nmax 100010
int index[nmax],lowLink[nmax];
stack<int> s;
vector<int> graph[nmax];
vector< vector<int> > components;
int nodes,edges,to,from,NumberOfNodes=1;
vector<bool> InStack(nmax);
void Tarjan(int StartNode);
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%i %i", &nodes,&edges);
for(int i=0;i<edges;i++)
{
scanf("%i %i", &to,&from);
graph[from].push_back(to);
}
for(int i=1;i<=nodes;i++)
{
if(index[i]==0)
{
Tarjan(i);
}
}
printf("%i\n", components.size());
for(int i=0;i<components.size();i++)
{
for(int j=components[i].size()-1;j>=0;j--)
{
printf("%i ", components[i][j]);
}
printf("\n");
}
int i;
//scanf("%i", &i);
return 0;
}
void Tarjan(int StartNode)
{
index[StartNode]=lowLink[StartNode]=NumberOfNodes++;
s.push(StartNode);
InStack[StartNode]=true;
vector<int> :: iterator it;
for(it=graph[StartNode].begin();it!=graph[StartNode].end();++it)
{
if(index[*it]==0)
{
Tarjan(*it);
lowLink[StartNode]=min(lowLink[StartNode],lowLink[*it]);
}else
{
if(InStack[*it]==true)
{
lowLink[StartNode]=min(lowLink[StartNode],index[*it]);
}
}
}
if(index[StartNode]==lowLink[StartNode])
{
vector<int> NewComponent;
int node=0;
while(node!=StartNode)
{
node=s.top();
s.pop();
InStack[node]=false;
NewComponent.push_back(node);
}
components.push_back(NewComponent);
}
}