Pagini recente » Cod sursa (job #2126024) | Cod sursa (job #2900332) | Cod sursa (job #1603140) | Cod sursa (job #610663) | Cod sursa (job #2422215)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
std::vector<int> v[100500];
bool vis[100500];
bool ins[100500];
std::stack<int> s;
int disc[100500];
int low[100500];
int n,m;
int countt;
std::vector<int> rez[100500];
int rezc;
void specDFS(int u)
{
vis[u]=true;
ins[u]=true;
s.push(u);
if(disc[u]==0)
disc[u]=low[u]=++countt;
//std::cout<<u<<"\n";
for(int i=0;i<v[u].size();i++)
{
int elem=v[u][i];
if(!vis[elem])
{
specDFS(elem);
low[u]=std::min(low[u],low[elem]);
}
else if(vis[elem]&& ins[elem] )
low[u]=std::min(low[u],disc[elem]);
}
if(disc[u]==low[u])
{
rezc++;
rez[rezc-1]= std::vector<int>();
while(s.top()!=u)
{
rez[rezc-1].push_back(s.top());
ins[s.top()]=false;
s.pop();
}
rez[rezc-1].push_back(s.top());
s.pop();
ins[u]=false;
}
// std::cout<<"end:"<<u<<"\n";
}
int main()
{
fin>>n>>m;
for(int i=0;i<m;i++)
{
int j,k;
fin>>j>>k;
v[j].push_back(k);
}
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
specDFS(i);
}
fout<<rezc<<"\n";
for(int i=0;i<rezc;i++)
{
for(int j=0;j<rez[i].size();j++)
fout<<rez[i][j]<<" ";
fout<<"\n";
}
}