Pagini recente » Cod sursa (job #2156025) | Cod sursa (job #1723852) | Cod sursa (job #289034) | Cod sursa (job #1559842) | Cod sursa (job #1707894)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<vector<int> > scc,gr;
int n,m,idx=1;
vector<int> index,low_index,in_stack,com;
stack<int> stiva;
void tarjan(int nod)
{
int i,j;
index[nod]=idx;
low_index[nod]=idx;
idx++;
stiva.push(nod);
in_stack[nod]=1;
for(i=0;i<gr[nod].size();i++)
{
if(index[gr[nod][i]]==-1)
{
tarjan(gr[nod][i]);
low_index[nod]=min(low_index[nod],low_index[gr[nod][i]]);
}
else
{
if(in_stack[gr[nod][i]]==1)
{
low_index[nod]=min(low_index[nod],low_index[gr[nod][i]]);
}
}
}
if(low_index[nod]==index[nod])
{
int aux;
com.clear();
do
{
aux=stiva.top();
stiva.pop();
com.push_back(aux);
in_stack[aux]=0;
}
while(aux!=nod);
scc.push_back(com);
}
}
int main()
{
int i,j,x,y,z;
f>>n>>m;
gr.resize(n+1);
index.resize(n+1,-1);
low_index.resize(n+1,1000000);
in_stack.resize(n+1);
scc.clear();
for(i=1;i<=m;i++)
{
f>>x>>y;
gr[x].push_back(y);
//in[y].push_back(x);
}
for(i=1;i<=n;i++)
if(index[i]==-1)
tarjan(i);
g<<scc.size()<<"\n";
for(i=0;i<scc.size();i++)
{
for(j=0;j<scc[i].size();j++)
g<<scc[i][j]<<" ";
g<<"\n";
}
}