Pagini recente » Cod sursa (job #775967) | Cod sursa (job #2925289) | Cod sursa (job #2164689) | Cod sursa (job #961972) | Cod sursa (job #3245740)
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int nmax=1e5, mmax=2e5;
int n, m;
vector <int> graph[nmax+1];
vector <int> level(nmax+1, 0), min_acces_level(nmax+1, 0);
vector <vector<int>> component;
bitset <nmax+1> vis;
void read()
{
int a, b;
in>>n>>m;
for(int i=1; i<=m; i++)
{
in>>a>>b;
graph[a].push_back(b);
graph[b].push_back(a);
}
}
stack <int> s;
int timp=0;
void dfs(int child, int parent)
{
vis[child]=true;
s.push(child);//nodurile in ordinea parcurgerii dfs
//timp++;
//level[child]=timp;
level[child]=level[parent]+1;
min_acces_level[child]=level[child];
for(int neighbor_of_child:graph[child])
{
if(neighbor_of_child != parent)
{
if(vis[neighbor_of_child]==1)//muchie de intoarcere
{
if(min_acces_level[child] > level[neighbor_of_child])
min_acces_level[child] = level[neighbor_of_child];
}
else
{
dfs(neighbor_of_child, child);
if(min_acces_level[child] > min_acces_level[neighbor_of_child])
min_acces_level[child] = min_acces_level[neighbor_of_child];
//child are un vecin care are nivelul mai mic decat poate atinge el
if(min_acces_level[neighbor_of_child] >= level[child])
{
vector <int> curr;
//totul din stiva pana la acel vecin inclusiv este in aceeasi componenta conexa
while(!s.empty() && s.top() != neighbor_of_child)
{
curr.push_back(s.top());
s.pop();
}
if(!s.empty())
s.pop();
curr.push_back(neighbor_of_child);
curr.push_back(child);
component.push_back(curr);
}
}
}
}
}
void display()
{
out<<component.size()<<'\n';
for(int i=0; i<component.size(); i++)
{
for(int j=component[i].size()-1; j>=0; j--)
out<<component[i][j]<<" ";
out<<'\n';
}
}
int main()
{
read();
dfs(1, 0);
display();
}