Pagini recente » Cod sursa (job #2834718) | Cod sursa (job #2425507) | Cod sursa (job #1077947) | Cod sursa (job #481846) | Cod sursa (job #1263206)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n,m,i,j,x,y,nod,nr,nr_comp,st;
int d[100005],ordine[100005];
bool fol[100005],fol_cr[100005],ok;
vector<int> graf[100005],graft[100005],rasp[100005];
void bfs(int nod)
{
for(int i=0; i<graf[nod].size(); i++)
{
if(!fol[graf[nod][i]])
{
fol[graf[nod][i]]=1;
d[graf[nod][i]]=nr-1; nr--;
bfs(graf[nod][i]);
}
}
}
void bfs_t(int nod)
{
int i,x;
if(nod==st && fol[nod])
ok=true;
for(i=0; i<graft[nod].size(); i++)
{
x=graft[nod][i];
if(!fol[graft[nod][i]] && !fol_cr[graft[nod][i]])
{
fol[graft[nod][i]]=1;
fol_cr[graft[nod][i]]=1;
bfs_t(graft[nod][i]);
if(ok==false)
fol[graft[nod][i]]=0;
else
rasp[nr_comp].push_back(graft[nod][i]);
}
}
}
int main()
{
cin>>n>>m;
for(i=1; i<=m; i++)
{
cin>>x>>y;
graf[x].push_back(y); // graful normal
graft[y].push_back(x); // graful transpus
}
d[1]=n; fol[1]=1; nr=n;
bfs(1); // fac bfs si atrbui in d[i] timpul la care a fost prelucrat nodu i ( ordine descrescatoare )
for(i=1; i<=n; i++) // sortez nodurile in ordine descrescatoare
ordine[n-d[i]+1]=i;
nr_comp=0;
for(i=1; i<=n; i++)
fol[i]=0;
for(i=1; i<=n; i++)
{
if(!fol[ordine[i]])
{
for(j=1; j<=n; j++)
fol_cr[j]=0;
++nr_comp;
st=ordine[i]; ok=false;
bfs_t(ordine[i]);
if(!ok)
{
rasp[nr_comp].push_back(ordine[i]);
fol[ordine[i]]=1;
}
}
}
cout<<nr_comp<<"\n";
for(i=1; i<=nr_comp; i++)
{
for(j=0; j<rasp[i].size(); j++)
cout<<rasp[i][j]<<" ";
cout<<"\n";
}
}