Pagini recente » Cod sursa (job #1318647) | Cod sursa (job #2777621) | Cod sursa (job #2054910) | Cod sursa (job #2619837) | Cod sursa (job #2157123)
#include<cstdio>
#include<vector>
#include<stack>
#include<set>
#define MAX_N 100000
using namespace std;
vector<int>g[MAX_N + 1], comp[MAX_N + 1];
stack<pair<int, int> >st;
set< int > s;
int visitedTime[MAX_N + 1], lowTime[MAX_N + 1], p[MAX_N + 1], n, m, time, nr;
bool visited[MAX_N + 1];
void readGraph() {
int x, y;
FILE *fin = fopen("biconex.in","r");
fscanf(fin,"%d%d",&n,&m);
for(int i = 0; i < m; i++) {
fscanf(fin,"%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
fclose(fin);
}
void popStack(int x, int y) {
set<int>::iterator it;
int i, j;
do {
i = st.top().first;
j = st.top().second;
st.pop();
s.insert(i);
s.insert(j);
}while(x != i || y != j);
for(it = s.begin(); it != s.end(); it++)
comp[nr].push_back(*it);
nr++;
s.clear();
}
void DFS(int node) {
vector<int>::iterator it;
visited[node] = true;
visitedTime[node] = lowTime[node] = time++;
for(it = g[node].begin(); it != g[node].end(); it++) {
if(p[node] == *it)
continue;
if(!visited[*it]) {
p[*it] = node;
st.push(make_pair(node,*it));
DFS(*it);
if(visitedTime[node] <= lowTime[*it])
popStack(node,*it); // node este punct de articulatie
// eliminam muchiile din stiva pana la intalnirea muchiei (node, *it)
else lowTime[node] = min(lowTime[node],lowTime[*it]);
} else lowTime[node] = min(lowTime[node],visitedTime[*it]);
}
}
void printComp() {
FILE *fout = fopen("biconex.out","w");
fprintf(fout,"%d\n",nr);
for(int i = 0; i < nr; i++) {
for(int j = 0; j < comp[i].size(); j++)
fprintf(fout,"%d ",comp[i][j]);
fprintf(fout,"\n");
}
fclose(fout);
}
int main() {
readGraph();
DFS(1);
printComp();
return 0;
}