Pagini recente » Cod sursa (job #3126971) | Cod sursa (job #1639205) | Cod sursa (job #28702) | Cod sursa (job #3190429) | Cod sursa (job #2157097)
#include<cstdio>
#include<vector>
#include<stack>
#define MAX_N 100000
using namespace std;
vector<int>g[MAX_N + 1], comp[MAX_N + 1];
stack<pair<int, int> >st;
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) {
bool ok;
vector<int>sol;
vector<int>::iterator it;
vector<int>::iterator it2;
int i, j;
do {
i = st.top().first;
j = st.top().second;
st.pop();
sol.push_back(i), sol.push_back(j);
}while(x != i || y != j);
for(it = sol.begin(); it != sol.end(); it++) {
ok = false;
for(it2 = comp[nr].begin(); it2 != comp[nr].end() && !ok; it2++)
if(*it2 == *it)
ok = true;
if(!ok)
comp[nr].push_back(*it);
}
nr++;
}
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;
}