Pagini recente » Cod sursa (job #1305172) | Cod sursa (job #2889310) | Cod sursa (job #786712) | Cod sursa (job #785708) | Cod sursa (job #1131895)
//
// main.cpp
// ctc
//
// Created by Catalina Brinza on 3/1/14.
// Copyright (c) 2014 Catalina Brinza. All rights reserved.
//
#include <fstream>
#include <vector>
#include <stack>
#define nr 100002
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> v[nr];
vector <bool> visit, instack;
vector <int> c,ind;
int low[nr];
int k=0;
stack <int> s;
vector <vector<int>> liste;
void tarjan(int i)
{
low[i]=k;
ind[i]=k;
k++;
s.push(i);
instack[i]=true;
for (int j=0;j<v[i].size();++j)
if (ind[v[i][j]]==-1)
{
tarjan(v[i][j]);
if (low[v[i][j]]<low[i]) low [i]=low [v[i][j]];
}
else if (instack[v[i][j]] && low[v[i][j]]<low[i]) low [i]=low[v[i][j]];
if (low[i]==ind[i])
{
c.clear();
while (i!=s.top())
{
c.push_back(s.top());
instack[s.top()]=false;
s.pop();
}
c.push_back(i);
instack[i]=false;
s.pop();
liste.push_back(c);
}
return;
}
int main(int argc, const char * argv[])
{int n,m,i,x,y,j;
f>>n>>m;
for (i=0;i<m;++i)
{
f>>x>>y;
v[x].push_back(y);
}
for (i=1;i<=n+1;++i)
{
visit.push_back(false);
instack.push_back(false);
ind.push_back(-1);
}
for (i=1;i<=n;++i)
if (ind[i]==-1) tarjan(i);
g<<liste.size()<<"\n";
for (i=0;i<=liste.size();++i)
{
for (j=0;j<liste[i].size();++j) g<<liste[i][j]<<' ';
g<<"\n";
}
return 0;
}