Mai intai trebuie sa te autentifici.
Cod sursa(job #2272615)
Utilizator | Data | 30 octombrie 2018 14:21:11 | |
---|---|---|---|
Problema | Componente tare conexe | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.18 kb |
#include <cstdio>
#include <vector>
#include <iostream>
#define DIMN 100001
using namespace std;
int g,sol,elem,niv[DIMN],low[DIMN],s[DIMN],f[DIMN];
vector <int> v[DIMN],sl[DIMN];
void dfs (int nod){
int vecin,i;
g++;
niv[nod]=g;
low[nod]=g;
s[++elem]=nod;
f[nod]=1;
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (!niv[vecin]){
dfs(vecin);
low[nod]=min(low[nod],low[vecin]);
}
else if (f[nod])
low[nod]=min(low[nod],low[vecin]);
}
if (low[nod]==niv[nod]){
sol++;
do{
sl[sol].push_back(s[elem]);
f[s[elem]]=0;
elem--;
} while (s[elem+1]!=nod);
}
}
int main()
{
FILE *fin=fopen ("ctc.in","r");
FILE *fout=fopen ("ctc.out","w");
int n,m,x,y,i,j;
fscanf (fin,"%d%d",&n,&m);
for (i=1;i<=m;i++){
fscanf (fin,"%d%d",&x,&y);
v[x].push_back(y);
}
dfs (1);
fprintf (fout,"%d\n",sol);
for (i=1;i<=sol;i++){
for (j=0;j<sl[i].size();j++)
fprintf (fout,"%d ",sl[i][j]);
fprintf (fout,"\n");
}
return 0;
}