Pagini recente » Cod sursa (job #3206876) | Cod sursa (job #3241644) | aqdafs | Cod sursa (job #1290784) | Cod sursa (job #1288743)
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstdio>
#define N 100005
#define M 200005
bool stack[N];
int index[N];
int min[N];
int contor = 1;
std::stack<int> s;
std::vector<std::vector<int> > v;
std::vector<std::vector<int> >components;
void dfs(int k)
{
s.push(k);
index[k] = min[k] = contor++;
for(auto& e: v[k])
{
if(not index[e])
{
dfs(e);
}
min[k] = std::min(min[k], min[e]);
}
if(min[k] == index[k])
{
std::vector<int> component;
while(s.top()!=k)
{
component.push_back(s.top());
s.pop();
}
component.push_back(k);
s.pop();
components.push_back(component);
}
}
int main ()
{
FILE *fin=fopen("ctc.in","r");
FILE *fout=fopen("ctc.out","w");
int n,m,a,b;
fscanf(fin, "%d%d", &n, &m);
v.resize(n+1);
for(int i=0;i<m;i++)
{
fscanf(fin, "%d%d", &a, &b);
v[a].push_back(b);
}
for(int i=1;i<=n;i++)
{
if(not index[i])
{
dfs(i);
}
}
std::cout<<components.size()<<std::endl;
for(auto& component: components)
{
for(auto& e: component)
{
std::cout<<e<<" ";
}
std::cout<<std::endl;
}
return 0;
}