Pagini recente » Cod sursa (job #1700100) | Cod sursa (job #1482937) | Cod sursa (job #874113) | Cod sursa (job #842100) | Cod sursa (job #2278761)
#include <bits/stdc++.h>
#include <iterator>
#define MAXn 100000
#define UNVISITED -1
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> v[MAXn+1];
stack<int> s;
bool onstack[MAXn+1];
int id[MAXn+1],low[MAXn+1];
int ID,n,m,nr;
vector< vector<int> >rez;
vector <int> c;
void tarjan(int i)
{
id[i]=low[i]=ID++;
s.push(i);
onstack[i]=true;
for(vector<int>::iterator it=v[i].begin();it!=v[i].end();it++)
{
if(id[*it]==UNVISITED)
tarjan(*it);
if(onstack[*it])
low[i]=min(low[i],low[*it]);
}
if(id[i]==low[i])
{
c.clear();
int node;
do
{
c.push_back(s.top());
node=s.top();
onstack[node]=false;
s.pop();
}while(node!=i);
rez.push_back(c);
nr++;
}
}
int main()
{
f>>n>>m;
int a,b;
for(int i=1;i<=m;i++)
{
f>>a>>b;
v[a].push_back(b);
}
for(int i=1;i<=n;i++)
id[i]=UNVISITED;
for(int i=1;i<=n;i++)
if(id[i]==UNVISITED)
{
tarjan(i);
}
g<<nr;
for(size_t i=0;i<rez.size();i++)
{
g<<'\n';
for(size_t j=0;j<rez[i].size();j++)
g<<rez[i][j]<<' ';
}
f.close();
g.close();
return 0;
}