Pagini recente » Cod sursa (job #362300) | Cod sursa (job #2126295) | Cod sursa (job #2555462) | Cod sursa (job #1358699) | Cod sursa (job #2858465)
#include <fstream>
#include <vector>
#define NMAX 100003
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n,m,k,niv,cnt;
int stiv[NMAX];
int nivel[NMAX],lw[NMAX];
bool viz[NMAX];
vector<int> compConex[NMAX];
vector<int>graf[NMAX];
void dfs(int nod)
{
viz[nod]=true;
stiv[++k]=nod;
nivel[nod]=++niv;
lw[nod]=niv;
for(int i=0; i<graf[nod].size(); i++)
{
int nd=graf[nod][i];
if(nivel[nd]==0)
{
dfs(nd);
lw[nod]=min(lw[nod],lw[nd]);
}
else if(viz[nd]){
lw[nod]=min(lw[nod],nivel[nd]);//muchie de intoarcere
}
}
if(lw[nod]==nivel[nod])
{
//e cmp conexa
cnt++;
do{
compConex[cnt].push_back(stiv[k]);
viz[stiv[k]]=false;
k--;
}while(k>0 && stiv[k+1]!=nod);
}
//fout<<nod;
}
int main()
{
fin>>n>>m;
for(int i=1; i<=m; i++)
{
int x,y;
fin>>x>>y;
graf[x].push_back(y);
}
for(int i=1; i<=n; i++)
{
if(nivel[i]==0)
{
dfs(i);
}
}
fout<<cnt<<"\n";
for(int i=1; i<=cnt; i++)
{
for(int j=0; j<compConex[i].size(); j++)
{
fout<<compConex[i][j]<<" ";
}
fout<<"\n";
}
return 0;
}