Pagini recente » Cod sursa (job #1153776) | Cod sursa (job #507430) | Cod sursa (job #1457725) | Cod sursa (job #2297255) | Cod sursa (job #2813633)
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
class Graph{
private:
vector< vector<int> > listaAdiacenta;
vector< vector<int> > listaAdiacentaT;
vector<int> vizitat;
vector<int> vizitatT;
stack <int> Stiva;
vector < vector<int> > componente;
int n;
public:
Graph(int n1) : n(n1){
this->listaAdiacenta.resize(n1 + 1);
this->listaAdiacentaT.resize(n1 + 1);
this->vizitat.resize(n1 + 1);
this->vizitatT.resize(n1 + 1);
this->componente.resize(n1 + 1);
for(int i = 0;i<=n1;++i)vizitat[i] = vizitatT[i] = 0;
};
void adaugMuchie(int deLa, int la){
this->listaAdiacenta[deLa].push_back(la);
}
void adaugMuchieT(int deLa, int la){
this->listaAdiacentaT[deLa].push_back(la);
}
void dfs(int varf){
vizitat[varf] = true;
for (int p: listaAdiacenta[varf]) {
if(!vizitat[p]){
dfs(p);
}
}
}
void dfs1(int varf){
vizitat[varf] = 1;
for (int p: listaAdiacenta[varf]) {
if(!vizitat[p]){
dfs1(p);
}
}
Stiva.push(varf);
}
void dfs2(int varf, int contorComp){
vizitatT[varf] = 1;
componente[contorComp].push_back(varf);
for (int p: listaAdiacentaT[varf]) {
if(!vizitatT[p]){
dfs2(p, contorComp);
}
}
}
int nrComponenteConexe(){
int contor = 0;
for(int i = 1;i<=n;++i){
if(!vizitat[i]){
++contor;
dfs(i);
}
}
return contor;
}
void print(){
for (int i = 1; i <= n; i++)
{
// print the current vertex number
cout << i << " ---> ";
// print all neighboring vertices of a vertex `i`
for (int v: listaAdiacenta[i]) {
cout << v << " ";
}
cout << endl;
}
}
void bfs(int startNo){
int prim, ultim, i;
queue <int> q;
q.push(startNo);
vizitat[startNo] = 1;
while (!q.empty()){
int nodAcutal = q.front();
q.pop();
for (int p: listaAdiacenta[nodAcutal]) {
if(vizitat[p] == 0){
vizitat[p] = vizitat[nodAcutal] + 1;
q.push(p);
}
}
}
}
void afisareVizitat(){
for(int i = 1;i<=n;++i)fout<<vizitat[i] - 1<<" ";
}
void componenteTare(){
for(int i = 1;i<=n;++i){
if(!vizitat[i]){
dfs1(i);
}
}
int contorComp = 0;
while(!Stiva.empty()){
int varf = Stiva.top();
Stiva.pop(); /// nu l mai folosim
if(!vizitatT[varf]){
contorComp++;
dfs2(varf, contorComp);
}
}
fout<<contorComp<<endl;
for(int i = 1;i<=contorComp;++i){
int lungime = componente[i].size();
for (int j = 0;j<lungime;++j){
fout<<componente[i][j]<<" ";
}
fout<<endl;
}
}
};
int main()
{
int n, m;
fin>>n>>m;
Graph g(n);
for(int i = 1;i<=m;++i){
int a, b;
fin>>a>>b;
g.adaugMuchie(a, b);
g.adaugMuchieT(b, a);
}
g.componenteTare();
return 0;
}