Pagini recente » Cod sursa (job #2395686) | Cod sursa (job #849746) | Cod sursa (job #1731075) | Cod sursa (job #1546411) | Cod sursa (job #754454)
Cod sursa(job #754454)
#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
vector<int> v[100001];
vector<int> component[100001];
int counter = -1;
int depth[100001], low[100001];
stack<int> s;
inline void retrieve_component(int where, int next)
{
counter++;
while (true)
{
int y = s.top(); s.pop();
int x = s.top(); s.pop();
component[counter].push_back(x);
component[counter].push_back(y);
if (x == where && y == next)
break;
}
}
void dfs(int where, int parent, int d)
{
depth[where] = d;
low[where] = d;
for (int nn=0; nn<(int)v[where].size(); nn++)
{
int next = v[where][nn];
if (next == parent)
continue;
if (depth[next] >= 0)
{
low[where] = min(low[where], depth[next]);
s.push(where);
s.push(next);
} else
{
s.push(where);
s.push(next);
dfs(next, where, depth[where] + 1);
low[where] =min(low[where], low[next]);
if (low[next] >= depth[where])
{
retrieve_component(where, next);
}
}
}
}
int main()
{
FILE *input = fopen("biconex.in", "r");
FILE *output = fopen("biconex.out", "w");
int n, m;
fscanf(input, "%d %d", &n, &m);
for (int i=0; i<m; i++)
{
int a, b;
fscanf(input, "%d %d", &a, &b);
a--; b--;
v[a].push_back(b);
v[b].push_back(a);
}
memset(depth, -1, sizeof(depth));
memset(low, -1, sizeof(low));
dfs(0, -1, 0);
fprintf(output, "%d\n", counter+1);
for (int zz=0; zz<counter+1; zz++)
{
sort(component[zz].begin(), component[zz].end());
component[zz].erase(unique(component[zz].begin(), component[zz].end()), component[zz].end());
for (int kk=0; kk<(int)component[zz].size(); kk++)
{
if (kk == 0)
fprintf(output, "%d", (component[zz][kk]+1));
else
fprintf(output, " %d", (component[zz][kk]+1));
}
fprintf(output, "\n");
}
fclose(input);
fclose(output);
system("pause");
return 0;
}