Cod sursa(job #2649208)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 13 septembrie 2020 15:16:03
Problema Cuplaj maxim in graf bipartit Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

int n, m, ansCount;
int low[100100], level[100100];
bool fr[100100];
vector<vector<int>> adj, ans;
stack<int> s;

void addAns(int stopper)
{
    while(s.top() != stopper)
    {
        ans[ansCount].push_back(s.top());
        s.pop();
    }

    ans[ansCount].push_back(s.top());
}

void solve(int node, int father)
{
    fr[node] = true;
    level[node] = level[father] + 1;
    low[node] = level[father];

    //int sons = 0;

    s.push(node);

    cout << node << '\n';

    for(auto it : adj[node])
    {
        if(it == father)
            continue;

        if(fr[it] == true)
            low[node] = min(low[node], level[it]);
        else
        {
            solve(it, node);

            if(level[node] <= low[it])
            {
                ansCount++;

                addAns(node);
            }

            low[node] = min(low[node], low[it]);
        }
    }

    /*if(father == 0 && sons > 1)
    {
        ansCount++;

        addAns(node);
    }*/
}

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

    adj.resize(n + 5);
    ans.resize(n + 5);

    for(int i = 1; i <= m; i++)
    {
        int x, y;
        in >> x >> y;

        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    solve(1, 0);

    out << ansCount << '\n';

    for(int i = 1; i <= ansCount; i++)
    {
        int len = ans[i].size();

        for(int j = 0; j < len; j++)
            out << ans[i][j] << ' ';

        out << '\n';
    }

    return 0;
}