Cod sursa(job #3194151)

Utilizator matei__bBenchea Matei matei__b Data 17 ianuarie 2024 10:05:38
Problema Componente biconexe Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.7 kb
#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;
}