Pagini recente » Cod sursa (job #2678823) | Cod sursa (job #517295) | Cod sursa (job #612594) | Cod sursa (job #12511) | Cod sursa (job #3194151)
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define chad char
#define mod 1'000'000'007
#define dim 100005
#define lim 1000000
#define mdim 1501
#define mult 2e9
#define maxx 200002
#define simaimult 1e17
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define pli pair<ll,int>
#define pil pair<int,ll>
#define piii pair<int,pair<int,int> >
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define nr_biti __builtin_popcount
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m;
vector<pii> g[3*dim];
int st[3*dim],low[3*dim];
bool viz[3*dim];
bool art[3*dim];
int timer;
deque<piii> curr;
set<int> comp[3*dim];
bool oke[3*dim];
int nr_c;
void dfs(int nod,int daddy=0)
{
st[nod]=low[nod]=++timer;
viz[nod]=1;
int sons=0;
for(auto it:g[nod])
{
if(it.first==daddy)
continue;
if(viz[it.first])
{
low[nod]=min(low[nod],st[it.first]);
if(st[it.first]<st[nod])
curr.pb(mp(it.second,mp(nod,it.first)));
}
else
{
++sons;
curr.pb(mp(it.second,mp(nod,it.first)));
dfs(it.first,nod);
low[nod]=min(low[it.first],low[nod]);
if(daddy!=0 && low[it.first]>=st[nod])
art[nod]=1;
if(daddy==0 && sons>1)
art[nod]=1;
if(art[nod])
{
++nr_c;
while(curr.back().second.first!=nod || curr.back().second.second!=it.first)
{
//cout << curr.back().first << " " << curr.back().second << " | ";
oke[nr_c]|=curr.back().first;
comp[nr_c].insert(curr.back().second.first);
comp[nr_c].insert(curr.back().second.second);
curr.pop_back();
}
//cout << curr.back().first << " " << curr.back().second << " | ";
oke[nr_c]|=curr.back().first;
comp[nr_c].insert(curr.back().second.first);
comp[nr_c].insert(curr.back().second.second);
curr.pop_back();
}
}
}
}
vector<int> app[3*dim];
vector<int> t[3*dim];
bool sol,ans;
int nr1;
int eu,el;
void cauta(int nod)
{
if(sol)
return;
if(oke[nod])
nr1++;
if(nod==app[el][0])
{
ans=(nr1>0);
sol=1;
return;
}
viz[nod]=1;
for(auto it:t[nod])
{
if(!viz[it])
cauta(it);
}
if(oke[nod])
nr1--;
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(nullptr);
fout.tie(nullptr);
fin >> n >> m;
for(int i=1; i<=m; i++)
{
int x,y,este=0;
fin >> x >> y;
g[x].pb(mp(y,este));
g[y].pb(mp(x,este));
}
for(int i=1; i<=n; i++)
{
if(!viz[i])
{
if(!g[i].size())
{
++nr_c;
comp[nr_c].insert(i);
continue;
}
dfs(i);
}
if(curr.size())
{
++nr_c;
while(curr.size())
{
oke[nr_c]|=curr.back().first;
comp[nr_c].insert(curr.back().second.first);
comp[nr_c].insert(curr.back().second.second);
curr.pop_back();
}
}
}
fout << nr_c << "\n";
for(int i=1; i<=nr_c; i++)
{
for(auto it:comp[i])
fout << it << " ";
fout << "\n";
}
return 0;
}