Pagini recente » Cod sursa (job #1034561) | Cod sursa (job #2530223) | Cod sursa (job #3270643) | Cod sursa (job #2665759) | Cod sursa (job #2798460)
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
class Graf
{
private:
int numar_noduri, numar_muchii, numar_componente = 0;
vector <int> lista_adiacenta1[100001];
vector <int> lista_adiacenta2[100001];
vector <int> componenta[100001];
vector <int> st;
unordered_map <int, bool> vizitare1, vizitare2;
public:
void citire();
void parcurgere();
void dfs1(int);
void dfs2(int);
};
void Graf :: citire()
{
int capat_stang, capat_drept;
fin >> numar_noduri >> numar_muchii;
for(int i = 1; i <= numar_muchii; i++)
{
fin >> capat_stang >> capat_drept;
lista_adiacenta1[capat_stang].push_back(capat_drept);
lista_adiacenta2[capat_drept].push_back(capat_stang);
}
}
void Graf :: dfs1(int nod)
{
vizitare1[nod] = true;
for(int i = 0; i < lista_adiacenta1[nod].size(); i++)
if(!vizitare1[lista_adiacenta1[nod][i]])
dfs1(lista_adiacenta1[nod][i]);
st.push_back(nod);
}
void Graf :: dfs2(int nod)
{
vizitare2[nod] = true;
componenta[numar_componente].push_back(nod);
for(int i = 0; i < lista_adiacenta2[nod].size(); i++)
if(!vizitare2[lista_adiacenta2[nod][i]])
dfs2(lista_adiacenta2[nod][i]);
}
void Graf :: parcurgere()
{
for(int i = 1; i <= numar_noduri; i++)
if(!vizitare1[i])
dfs1(i);
for(int i = st.size() - 1; i >= 0; i--)
if(!vizitare2[st[i]])
{
dfs2(st[i]);
numar_componente++;
}
fout << numar_componente << '\n';
for(int i = 0; i < numar_componente; i++)
{
for(int j = 0; j < componenta[i].size(); j++)
fout << componenta[i][j] << " ";
fout << '\n';
}
}
int main()
{
Graf x;
x.citire();
x.parcurgere();
fin.close();
fout.close();
return 0;
}