Pagini recente » Cod sursa (job #2374914) | Cod sursa (job #2786750) | Cod sursa (job #1737714) | Rating Nu.se Stie (nusestie) | Cod sursa (job #1620745)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int dim = 2005;
int n;
int g[dim][dim];
vector<int> crit;
vector< pair<int, int> > critE, edges;
bool vis[dim];
void dfs(int node) {
vis[node] = true;
for (int i = 1; i <= n; ++i) {
if (g[node][i] != 1 || vis[i])
continue;
dfs(i);
}
}
bool isCrit(int node) {
for (int i = 1; i <= n; ++i)
if (g[node][i] == 1)
g[node][i] = g[i][node] = -1;
memset(vis, 0, sizeof vis);
vis[node] = true;
if (node != 1)
dfs(1);
else
dfs(2);
for (int i = 1; i <= n; ++i)
if (g[node][i] == -1)
g[node][i] = g[i][node] = 1;
for (int i = 1; i <= n; ++i)
if (!vis[i])
return true;
return false;
}
bool isCritE(int x, int y) {
g[x][y] = g[y][x] = 0;
memset(vis, 0, sizeof vis);
dfs(x);
g[x][y] = g[y][x] = 1;
for (int i = 1; i <= n; ++i)
if (!vis[i])
return true;
return false;
}
void dfs2(int node, vector<int> v, vector<int> &w) {
vis[node] = true;
w.push_back(node);
for (unsigned int i = 0; i < v.size(); ++i) {
if (!g[node][v[i]] || vis[v[i]])
continue;
dfs2(v[i], v, w);
}
}
void dfs3(int node, vector<int> v) {
vis[node] = true;
for (unsigned int i = 0; i < v.size(); ++i) {
if (g[node][v[i]] != 1 || vis[v[i]])
continue;
dfs3(v[i], v);
}
}
bool isCrit2(int node, vector<int> v) {
if (v.size() == 1)
return false;
for (int i = 1; i <= n; ++i)
if (g[node][i] == 1)
g[node][i] = g[i][node] = -1;
memset(vis, 0, sizeof vis);
vis[node] = true;
if (node != v.back())
dfs3(v.back(), v);
else
dfs3(v.front(), v);
for (int i = 1; i <= n; ++i)
if (g[node][i] == -1)
g[node][i] = g[i][node] = 1;
for (unsigned int i = 0; i < v.size(); ++i)
if (!vis[v[i]])
return true;
return false;
}
int bc;
vector<int> BC[dim];
void solve(vector<int> v) {
int root = 0;
for (unsigned int i = 0; i < v.size(); ++i)
if (isCrit2(v[i], v)) {root = v[i]; break;}
if (root == 0) {
++bc;
for (unsigned int i = 0; i < v.size(); ++i)
BC[bc].push_back(v[i]);
}
else {
memset(vis, 0, sizeof vis);
vis[root] = true;
vector<int> w;
vector< vector<int> > aux;
for (unsigned int i = 0; i < v.size(); ++i) {
if (!g[root][v[i]] || vis[v[i]])
continue;
w.clear();
w.push_back(root);
dfs2(v[i], v, w);
aux.push_back(w);
}
for (unsigned int i = 0; i < aux.size(); ++i)
solve(aux[i]);
}
}
int main() {
int p = 1;
// fin >> p;
int m;
fin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y;
fin >> x >> y;
edges.push_back(make_pair(x, y));
g[x][y] = g[y][x] = 1;
}
vector<int> v;
if(p == 1) {
for (int i = 1; i <= n; ++i)
v.push_back(i);
solve(v);
fout << bc << '\n';
for (int i = 1; i <= bc; ++i) {
//fout << BC[i].size() << ' ';
for (unsigned int j = 0; j < BC[i].size(); ++j)
fout << BC[i][j] << ' ';
fout << '\n';
}
}
else if (p == 2) {
for (int i = 1; i <= n; ++i)
if (isCrit(i))
crit.push_back(i);
fout << crit.size() << '\n';
for (unsigned int i = 0; i < crit.size(); ++i)
fout << crit[i] << ' ';
fout << '\n';
}
else {
for (int i = 0; i < m; ++i) {
if (isCritE(edges[i].first, edges[i].second))
critE.push_back(edges[i]);
}
fout << critE.size() << '\n';
for (unsigned int i = 0; i < critE.size(); ++i)
fout << critE[i].first << ' ' << critE[i].second << '\n';
}
return 0;
}
//Trust me, I'm the Doctor!