Mai intai trebuie sa te autentifici.
Cod sursa(job #3370374)
| Utilizator | Data | 25 octombrie 2026 19:58:53 | |
|---|---|---|---|
| Problema | Componente tare conexe | Scor | 0 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 1.15 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int noduri, muchii, x, y, nmax=100001, nr;
vector<vector<int>> graf[nmax], graftr[nmax];
int d[nmax], f[nmax];
vector<int> st[nmax];
int viz[nmax], final[nmax];
vector<int> ctc[nmax];
void read()
{
in>>noduri>>muchii;
graf.resize(noduri+1);
graftr.resize(noduri+1);
viz.resize(noduri+1);
final.resize(noduri+1);
for(int i=0;i<muchii;i++)
{
in>>x>>y;
graf[x].push_back(y);
graftr[y].push_back(x);
}
}
void dfs1(int nod)
{
viz[nod]=1;
for(auto nod_vecin : graf[nod])
{
if(viz[nod_vecin])
{
dfs(nod_vecin);
}
}
st.push_back(nod);
}
void dfs2(int nod)
{
final[nod]=1;
ctc[nr].push_back(nod);
for(int elem : graftr[nod])
{
if(!final[elem])
dfs2(elem);
}
}
int main()
{
read();
for(int i=0;i<noduri;i++)
{
if(!viz[i])
dfs1(i);
}
for(int cnt=0;cnt<st.size();cnt++)
{
x=st.pop();
if(!final[x])
{
nr++;
dfs2(x);
}
}
out<<nr<<'\n';
for(int i=0;i<ctc.size();i++)
{
for(int nod : ctc[i])
out<<nod<<" ";
out<<'\n';
}
}