Pagini recente » Monitorul de evaluare | Cod sursa (job #2359964) | Istoria paginii utilizator/iuliaotilia26 | Cod sursa (job #1573353) | Cod sursa (job #2011247)
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
#define DIM 100001
#define INF 2000000000
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
int n,m,nr;
vector<int> V[DIM];
int MIN[DIM];
int VIZ[DIM];
stack<int> S;
int ES[DIM];
vector<int> REZ[DIM];
int rez;
void dfs(int v)
{
VIZ[v]=MIN[v]=++nr;
S.push(v);
ES[v]=1;
for(int i=0;i<V[v].size();i++)
{
if(!VIZ[V[v][i]])
dfs(V[v][i]);
if(ES[V[v][i]])
MIN[v]=min(MIN[v],MIN[V[v][i]]);
}
if(VIZ[v]==MIN[v])
{
rez++;
while(!S.empty() && S.top()!=v)
{
REZ[rez].push_back(S.top());
ES[S.top()]=0;
S.pop();
}
REZ[rez].push_back(S.top());
ES[S.top()]=0;
S.pop();
}
}
int main()
{
fi>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
fi>>a>>b;
V[a].push_back(b);
}
for(int i=1;i<=n;i++)
MIN[i]=INF;
for(int i=1;i<=n;i++)
if(!VIZ[i])
dfs(i);
fo<<rez<<"\n";
for(int i=1;i<=rez;i++)
{
for(int j=0;j<REZ[i].size();j++)
fo<<REZ[i][j]<<" ";
fo<<"\n";
}
fi.close();
fo.close();
return 0;
}