Pagini recente » Cod sursa (job #2202553) | Cod sursa (job #1952563) | Cod sursa (job #2375718) | Cod sursa (job #2245090) | Cod sursa (job #631337)
Cod sursa(job #631337)
#include<iostream>
#include<fstream>
#include<string.h>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
#define NMAX 100050
const char infile[] = "biconex.in";
const char outfile[] = "biconex.out";
stack<pair<int, int> > StivaMuchii;
vector<int> Graph[NMAX];
vector<int> Componente[NMAX];
int NrComponente;
int N, M;
int S, T;
int NodCautat;
int nivel[NMAX];
int ancestor[NMAX];
void Citire();
void Afisare();
void Preproc();
void DFS(int startNode);
void Citire()
{
fstream fin(infile, ios::in);
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 << 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();
}
void Preproc()
{
memset(nivel, 0xFF, (N+1)<<2);
}
void DFS(int startNode)
{
ancestor[startNode] = nivel[startNode];
for(vector<int>::iterator itr = Graph[startNode].begin();
itr != Graph[startNode].end(); itr++)
{
if(nivel[*itr] == -1)
{
nivel[*itr] = nivel[startNode] +1;
StivaMuchii.push(make_pair(startNode, *itr));
DFS(*itr);
if(ancestor[*itr] >= nivel[startNode])
{
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++;
}
ancestor[startNode] = ancestor[startNode] < ancestor[*itr] ? ancestor[startNode] : ancestor[*itr];
}
else
{
if(nivel[startNode] > nivel[*itr] +1)
ancestor[startNode] = ancestor[startNode] < ancestor[*itr] ? ancestor[startNode] : ancestor[*itr];
}
}
}
int main(int argc, char* argv[])
{
Citire();
Preproc();
for(int i = 1 ; i <= N; i++)
{
if(nivel[i] == -1)
{
nivel[i] = 0;
DFS(i);
}
}
Afisare();
}