Pagini recente » Cod sursa (job #434658) | Cod sursa (job #1550695) | Cod sursa (job #454501) | Cod sursa (job #388579) | Cod sursa (job #1675956)
/**
* Worg
*/
#include <stack>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
FILE *fin = freopen("biconex.in", "r", stdin);
FILE *fout = freopen("biconex.out", "w", stdout);
const int bufferDim = 100000;
const int MAX_N = 1 + 100000;
class inputReader {
private:
char buffer[bufferDim];
int pos = 0;
bool digit(char c) {
return('0' <= c && c <= '9');
}
public:
void getBuffer() {
fread(buffer, 1, bufferDim, stdin);
pos = 0;
}
void getInt(int &nr) {
nr = 0;
while(!digit(buffer[pos]))
if(++pos == bufferDim)
getBuffer();
while(digit(buffer[pos])) {
nr = nr * 10 + buffer[pos] - '0';
if(++pos == bufferDim)
getBuffer();
}
}
} cin;
/*---------------------*/
int N, M;
vector<int> G[MAX_N];
/*---------------------*/
stack< pair<int,int> > S;
vector< vector<int> > comp;
vector<int> now;
int level[MAX_N], dp[MAX_N];
/*---------------------*/
void readData() {
cin.getBuffer();
cin.getInt(N); cin.getInt(M);
for(int i = 1; i <= M; ++i) {
int u, v; cin.getInt(u); cin.getInt(v);
G[u].push_back(v); G[v].push_back(u);
}
}
void newComponent(pair<int,int> stop) {
pair<int,int> top;
now.clear();
do {
top = S.top();
now.push_back(top.first); now.push_back(top.second);
S.pop();
}while(top != stop && !S.empty());
/* vrem sa eliminam dublurile */
sort(now.begin(), now.end());
now.erase(unique(now.begin(), now.end()), now.end());
comp.push_back(now);
}
void DFS(int node = 1, int father = 0) {
dp[node] = level[node];
for(vector<int>::iterator it = G[node].begin(); it != G[node].end(); ++it) {
if(!level[*it]) { /* daca nu am parcurs deja nodul */
level[*it] = level[node] + 1;
S.push(make_pair(node, *it));
DFS(*it, node);
if(dp[*it] >= level[node]) { /* daca nodul este critic */
newComponent(make_pair(node, *it));
}
}
}
for(vector<int>::iterator it = G[node].begin(); it != G[node].end(); ++it) {
if(*it != father) {
dp[node] = min(dp[node], dp[*it]);
}
}
}
void writeData() {
printf("%d\n", (int)comp.size());
for(int i = 0; i < (int)comp.size(); ++i) {
for(vector<int>::iterator it = comp[i].begin(); it != comp[i].end(); ++it) {
printf("%d ", *it);
}
printf("\n");
}
}
int main() {
readData();
level[1] = 1;
DFS();
writeData();
return 0;
}