Cod sursa(job #2399013)

Utilizator TudorCaloianCaloian Tudor-Ioan TudorCaloian Data 6 aprilie 2019 17:46:34
Problema Componente biconexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.07 kb

#include <bits/stdc++.h>
#define MOD 666013

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

int n, m, f[200005], d[200005], cnt, components[200005];
vector<int> v[200005];
stack <int> st;
bool in_stack[200005];
vector < vector <int> > ans;
void DFS(int nod, int last)
{
    f[nod] = d[nod] = ++cnt;
    st.push(nod);
    in_stack[nod] = 1;
    for(int i = 0; i < v[nod].size(); i++)
    {
        int child = v[nod][i];
        if(child == last) continue;

        if(!d[child])
            DFS(child, nod);

        if(in_stack[child])
        {
            vector <int> c;
            f[nod] = min(f[nod], f[child]);
            if(d[nod] <= f[child])
            {
                while(st.size() && st.top() != child)
                {
                    c.push_back(st.top());
                    components[st.top()]++;
                    components[st.top()]%=MOD;
                    in_stack[st.top()] = 0;
                    st.pop();

                }

                c.push_back(child);
                in_stack[child] = 0;
                c.push_back(nod);
                components[child]++;
                components[child]%=MOD;
                components[nod]++;
                components[nod]%=MOD;
                st.pop();

                ans.push_back(c);
            }
        }
    }

}

long long int pow(int k)
{
    long long int x, p;
    x = 1;
    p = 2;

    for(int i = 0; (1<<i) <= k; i++)
    {

        if(((1<<i)&k))
            x = (x*p)%MOD;
        p = (p*p)%MOD;
    }

    x -= 2;
    if(x<0)
        x+=MOD;
    return x;
}

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int a, b;
        fin >> a >> b;

        v[a].push_back(b);
        v[b].push_back(a);
    }

    DFS(1, 0);
    fout << ans.size() << '\n';
    for(int i = 0; i < ans.size(); i++)
    {
          for(int j = 0; j < ans[i].size(); j++)
            fout << ans[i][j] << " ";
        fout << '\n';

    }


    return 0;
}