Pagini recente » Cod sursa (job #2369875) | Cod sursa (job #1863897) | Cod sursa (job #2727717) | Cod sursa (job #2585378) | Cod sursa (job #631224)
Cod sursa(job #631224)
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
#define NMAX 100000
const char infile[] = "biconex.in";
const char outfile[] = "biconex.out";
stack<pair<int, int> > StivaMuchii;
vector<int> Graph[NMAX];
vector<int> Componente[NMAX];
bool isVizited[NMAX];
int NrComponente;
int N, M;
int S, T;
int NodCautat;
int nivel[NMAX];
int Parinte[NMAX];
void Citire();
void Afisare();
void DFS(int startNode);
void Compute(int startNodeIndex, int endNodeIndex);
void Citire()
{
fstream fin(infile, ios::in);
//fin >> S >> T;
fin >> N >> M;
int src, dst;
for(int i = 0 ; i < M; i++)
{
fin >> src >> dst;
Graph[src].push_back(dst);
Graph[dst].push_back(src);
}
fin.close();
}
void Afisare()
{
fstream fout(outfile, ios::out);
//fout << "Nodul cautat este = " << NodCautat << "\n";
fout << NrComponente << "\n";
for(int i = 0 ; i < NrComponente; i++)
{
for(vector<int>::reverse_iterator itr = Componente[i].rbegin();
itr != Componente[i].rend(); itr++)
{
fout << *itr << " ";
}
fout << "\n";
}
fout.close();
}
bool CannotAccessAncestor(int node, int ancestor)
{
if(nivel[node] >= nivel[ancestor])
{
return true;
}
return false;
}
void DFS(int startNode)
{
isVizited[startNode] = true;
for(vector<int>::iterator itr = Graph[startNode].begin();
itr != Graph[startNode].end(); itr++)
{
if(isVizited[*itr] == true && Parinte[startNode] != *itr)
{
nivel[startNode] = nivel[*itr];
}
else if(isVizited[*itr] == false)
{
Parinte[*itr] = startNode;
nivel[*itr] = nivel[startNode] +1;
StivaMuchii.push(make_pair(startNode, *itr));
DFS(*itr);
if(CannotAccessAncestor(*itr, startNode) == true)
{
pair<int, int> edge = make_pair(startNode, *itr);
while(StivaMuchii.top() != edge)
{
Componente[NrComponente].push_back(StivaMuchii.top().second);
StivaMuchii.pop();
}
Componente[NrComponente].push_back(StivaMuchii.top().second);
Componente[NrComponente].push_back(StivaMuchii.top().first);
StivaMuchii.pop();
NrComponente++;
}
if(nivel[startNode] > nivel[*itr])
{
nivel[startNode] = nivel[*itr];
}
}
}
}
int main(int argc, char* argv[])
{
Citire();
for(int i = 0 ; i < N; i++)
DFS(i);
Afisare();
}