Pagini recente » Cod sursa (job #2025933) | Cod sursa (job #1886574) | Cod sursa (job #1886776) | Cod sursa (job #389728) | Cod sursa (job #595816)
Cod sursa(job #595816)
#include <fstream>
#include <stack>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
vector <int> g[100005],con,idx,lowlink,in_stack;
vector < vector <int> > c;
stack <int> s;
int ind;
void tarjan(int x)
{
unsigned int i;
lowlink[x]=ind;
idx[x]=lowlink[x];
++ind;
s.push(x),in_stack[x]=1;
for (i=0;i<g[x].size();++i)
if (idx[g[x][i]]==-1)
{
tarjan(g[x][i]);
lowlink[x]=min(lowlink[x],lowlink[g[x][i]]);
}
else if (in_stack[g[x][i]])
lowlink[x]=min(lowlink[x],lowlink[g[x][i]]);
if (idx[x]==lowlink[x])
{
con.clear();
int node;
do
{
con.push_back(node=s.top());
s.pop(),in_stack[node]=0;
}
while (node!=x);
c.push_back(con);
}
}
int main(void)
{
int n,cnt_edges,x,y;
ifstream in("ctc.in");
ofstream out("ctc.out");
in>>n;
for (in>>cnt_edges;cnt_edges>0;--cnt_edges)
{
in>>x>>y;
g[x-1].push_back(y-1);
}
idx.resize(n),lowlink.resize(n),in_stack.resize(n);
idx.assign(n,-1),in_stack.assign(n,0);
for (int i=0;i<n;++i)
if (idx[i]==-1)
tarjan(i);
out<<c.size()<<"\n";
for (size_t i=0;i<c.size();++i)
{
for (size_t j=0;j<c[i].size();++j)
out<<c[i][j]+1<<" ";
out<<"\n";
}
return 0;
}