Pagini recente » Cod sursa (job #2973993) | Cod sursa (job #3037640) | Cod sursa (job #2447735) | Cod sursa (job #1480588) | Cod sursa (job #595813)
Cod sursa(job #595813)
#include <fstream>
#include <stack>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
vector <int> g[100005],con;
vector < vector <int> > c;
stack <int> s;
int index,in_stack[100005],idx[100005],lowlink[100005];
void tarjan(int x)
{
unsigned int i;
lowlink[x]=index;
idx[x]=lowlink[x];
++index;
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.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;
}