Pagini recente » Borderou de evaluare (job #337029) | Cod sursa (job #314644) | Cod sursa (job #625953) | Cod sursa (job #1905462) | Cod sursa (job #610573)
Cod sursa(job #610573)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
#define MAXN 100005
#define minimum(a,b) \
({\
typeof(a) _a = a; \
typeof(b) _b = b; \
_a<=_b?_a:_b; \
})
using namespace std;
typedef vector<vector<int> > Graph;
Graph graph;
int low[MAXN];
int discTime[MAXN];
stack<pair<int, int> > stEdges;
vector<vector<int> > BiComps;
void AddBiComp(const int x, const int y)
{
vector<int> comp;
while(!stEdges.empty())
{
const pair<int, int> edge = stEdges.top();
stEdges.pop();
comp.push_back(edge.first);
comp.push_back(edge.second);
if (edge.first == x && edge.second == y)
break;
}
if (comp.size())
BiComps.push_back(comp);
}
void AddLeftOver()
{
vector<int> comp;
while(!stEdges.empty())
{
const pair<int, int> edge = stEdges.top();
stEdges.pop();
comp.push_back(edge.first);
comp.push_back(edge.second);
}
if (comp.size())
BiComps.push_back(comp);
}
void DFS
(
const int node,
const int parent,
const int depth
)
{
vector<int>::iterator it;
discTime[node] = low[node] = depth;
for (it=graph[node].begin(); it!=graph[node].end(); ++it)
{
if (*it != parent)
{
if (discTime[*it] == -1)
{
stEdges.push(make_pair(node, *it));
DFS(*it, node, depth+1);
low[node] = minimum(low[node], low[*it]);
if (low[*it] >= discTime[node])
{
AddBiComp(node, *it);
}
}
else
{
low[node] = minimum(low[node], discTime[*it]);
}
}
}
}
int main()
{
int n,m;
fstream fin("biconex.in", fstream::in);
fstream fout("biconex.out", fstream::out);
fin >> n >> m;
//cout << n << " " << m << endl;
graph.resize(n);
for (int i=0; i<m; ++i)
{
int x, y;
fin >> x >> y;
graph[x-1].push_back(y-1);
graph[y-1].push_back(x-1);
discTime[i] = -1;
}
//memset(discTime, 0xFFFFFFFF, (n+1)*sizeof(int));
DFS(0,-1,0);
AddLeftOver();
fout << BiComps.size() << "\n";
for (int i=0; i<BiComps.size(); ++i)
{
sort(BiComps[i].begin(), BiComps[i].end());
BiComps[i].erase(unique(BiComps[i].begin(), BiComps[i].end()), BiComps[i].end());
for (int j=0; j<BiComps[i].size(); ++j)
{
fout << BiComps[i][j]+1 << " ";
}
fout << "\n";
}
fin.close();
fout.close();
return 0;
}