Cod sursa(job #2880129)

Utilizator Vali_nnnValentin Nimigean Vali_nnn Data 29 martie 2022 14:29:18
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
vector <int> a[100001];
vector <int> b[100001];
int i,j,n,m,v1[100001],v2[100001],k,x,y,ctc[10001],nr;
void dfs1(int p)
{v1[p]=1;
for(int q=0;q<a[p].size();q++)
{if(v1[a[p][q]]==0)
  dfs1(a[p][q]);
}

}
void dfs2(int p)
{v2[p]=1;
for(int q=0;q<b[p].size();q++)
{if(v2[b[p][q]]==0)
  dfs2(b[p][q]);
}

}
int main()
{f>>n>>m;
for(i=1;i<=m;i++)
{f>>x>>y;
a[x].push_back(y);
    b[y].push_back(x);
}

for(i=1;i<=n;i++)
{
    if(ctc[i]==0)
{for(j=1;j<=n;j++)
v2[j]=v1[j]=0;
    dfs1(i);
dfs2(i);
nr++;
for(j=1;j<=n;j++)
if(v2[j]==1&&v1[j]==1)
    ctc[j]=nr;
    for(j=1;j<=n;j++)
v1[j]=v2[j]=0;
}
}

g<<nr<<'\n';
for(i=1;i<=nr;i++ )
{for(j=1;j<=n;j++)
if(ctc[j]==i)
g<<j<<" ";
g<<'\n';}

}