Cod sursa(job #2814016)

Utilizator serafimalex2001Serafim Alex serafimalex2001 Data 7 decembrie 2021 13:22:23
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 16.05 kb
#include<bits/stdc++.h>
///bits?
using namespace std;

const int inf = (1e9);

const int dim = (1e5);

char buff[dim + 5];

int pos = 0;

int cnt[7505];

void read(int &nr) {
    int semn = 1;
    nr = 0;


    while (!isdigit(buff[pos])) {

        if (buff[pos] == '-') semn = -1;

        pos++;
        if (pos == dim) {
            pos = 0;
            fread(buff, 1, dim, stdin);
        }


    }


    while (isdigit(buff[pos])) {
        nr = nr * 10 + buff[pos] - '0';
        pos++;
        if (pos == dim) {
            pos = 0;
            fread(buff, 1, dim, stdin);
        }
    }

    nr *= semn;

}

bool cmp(pair<int, pair<int, int> > a, pair<int, pair<int, int> > b) {
    if (a.second.second == b.second.second)
        return make_pair(a.first, a.second.first) < make_pair(b.first, b.second.first);

    return a.second.second < b.second.second;
}


class DSU {
private:
    int m_nodes;
    vector<int> t;
public:
    DSU(int n) {
        m_nodes = n;
        t.resize(n + 5);
        for (int i = 0; i <= n; i++)
            t[i] = -1;
    }

    inline int getRoot(int x) {
        int y = x;
        while (t[y] > 0) y = t[y];

        int root = y;

        y = x;

        while (y != root) {
            int aux = t[y];
            t[y] = root;
            y = aux;
        }

        return root;
    }

    inline void unite(int x, int y) {
        if (t[x] < t[y]) {
            t[x] += t[y];
            t[y] = x;
        } else {
            t[y] += t[x];
            t[x] = y;
        }
    }

};

class Graph {

private:

    int m_nodes;

    vector <vector<pair < int, int>> > //lista de adiacenta pentru fiecare nod sub forma {vecin,cost}
    m_adjList;

    vector <pair<int, pair < int, int>> > //lista cu toate muchiile sub forma {nod1, {nod2, cost} }
    m_edges;

    vector<bool> m_visited; /// in functiile specifice in loc sa fie general pentru clasa?

    // vector<int> t;


    bool m_areLabeled;
    bool m_isDirected;
    //Ceva care sa retina daca e sau nu orientat

    struct tip {
        int nod;
        long long cost;

        bool operator<(const tip &other) const {
            return cost > other.cost;
        }
    };


    void topSort(vector<int> &solution, vector<bool> &seen, int node, int fat);

    void
    tarjan(vector<bool> &inStack, vector<int> &st, vector<int> &lvl, vector<int> &low, vector <vector<int>> &solution,
           int node, int fat, int &currentLevel);

    void bicoDFS(vector<int> &t, vector <vector<int>> &solution, vector<int> &st, vector<bool> &seen, vector<int> &lvl,
                 vector<int> &low, int node, int fat, int currentLevel);

    void depthDFS(vector<int> &d, int node);


    inline bool bfs(vector <vector<int>> &f, vector <vector<int>> &c, vector<int> &tt, int source, int destination);

public:

    Graph(int nodes, bool areLabeled, bool isDirected = false);


    void addEdge(int from, int to, int cost = 0);

    void resetVisited();

    vector<long long> dijkstra(int source);

    vector<int> bfs(int source);

    void dfs(int node);

    int getCC();


    vector <vector<int>> getSCCs();


    vector <vector<int>> getBiconected();

    vector <pair<int, int>> getCriticalEdges();

    vector<int> getTopSort();

    static bool HavelHakimi(vector<int> degSequence);


    pair<long long, vector<pair < int, int> > >

    getMST();

    pair<int, vector<long long> > bellmanFord(int source);

    vector <vector<int>> royFloyd();

    vector<int> getDepths(int root);

    int getTreeDiam();


    int getMaxFlow(vector <vector<int>> &c, int source, int destination);

};

void Graph::topSort(vector<int> &solution, vector<bool> &seen, int node, int fat) {

    seen[node] = 1;

    for (auto it: m_adjList[node]) {
        if (seen[it.first]) continue;
        if (it.first == fat) continue;

        topSort(solution, seen, it.first, node);
    }

    solution.push_back(node);
}

void Graph::tarjan(vector<bool> &inStack, vector<int> &st, vector<int> &lvl, vector<int> &low,
                   vector <vector<int>> &solution,
                   int node, int fat, int &currentLevel) {
    low[node] = lvl[node] = ++currentLevel;
    st.push_back(node);

    inStack[node] = 1;

    for (auto it: m_adjList[node]) {
        if (!lvl[it.first]) {
            tarjan(inStack, st, lvl, low, solution, it.first, node, currentLevel);
            low[node] = min(low[node], low[it.first]);
        } else if (inStack[it.first]) {
            low[node] = min(low[node], low[it.first]);
        }
    }


    if (low[node] == lvl[node]) {
        solution.push_back({});
        int x = -1;

        while (x != node) {
            x = st.back();
            solution.back().push_back(x);
            inStack[x] = 0;
            st.pop_back();
        }
    }

}

void
Graph::bicoDFS(vector<int> &t, vector <vector<int>> &solution, vector<int> &st, vector<bool> &seen, vector<int> &lvl,
               vector<int> &low, int node, int fat, int currentLevel) {
    st.push_back(node);
    low[node] = lvl[node] = currentLevel;

    seen[node] = 1;


    for (auto it: m_adjList[node]) {
        if (it.first == fat) continue;

        if (seen[it.first]) {
            low[node] = min(low[node], lvl[it.first]);
            continue;
        }

        t[it.first] = node;
        bicoDFS(t, solution, st, seen, lvl, low, it.first, node, currentLevel + 1);

        low[node] = min(low[node], low[it.first]);

        if (low[it.first] >= lvl[node]) {
            solution.push_back({});
            int x = 0;

            do {
                x = st.back();
                solution.back().push_back(x);
                st.pop_back();
            } while (x != it.first);

            solution.back().push_back(node);
            // exit(0);
        }

    }
}

void Graph::depthDFS(vector<int> &d, int node) {
    for (auto it: m_adjList[node]) {
        if (d[it.first]) continue;
        d[it.first] = 1 + d[node];

        depthDFS(d, it.first);
    }
}

bool Graph::bfs(vector <vector<int>> &f, vector <vector<int>> &c, vector<int> &tt, int source, int destination) {
    vector<bool> seen(m_nodes + 5, false);
    deque<int> q;

    q.push_back(source);

    seen[source] = 1;

    while (!q.empty()) {
        int nod = q.front();

        q.pop_front();

        for (auto it: m_adjList[nod]) {
            if (!seen[it.first] && f[nod][it.first] < c[nod][it.first]) {
                tt[it.first] = nod;
                seen[it.first] = 1;
                q.push_back(it.first);
            }
        }
    }

    return seen[destination];
}

Graph::Graph(int nodes, bool areLabeled, bool isDirected) {
    m_nodes = nodes;
    m_areLabeled = areLabeled;

    m_adjList.resize(nodes + 5);
    m_isDirected = isDirected;

    //t.resize(nodes + 5);

    //for (int i = 0; i <= nodes; i++)
    //  t[i] = -1;
}

void Graph::addEdge(int from, int to, int cost) {
    m_adjList[from].push_back(make_pair(to, cost));
    m_edges.push_back(make_pair(from, make_pair(to, cost)));
}


void Graph::resetVisited() {
    m_visited.resize(m_nodes + 5);

    for (int i = 0; i <= m_nodes; i++)
        m_visited[i] = 0;
}

vector<long long> Graph::dijkstra(int source) {

    priority_queue <tip> q;

    const long long inf = 10000000000LL;


    vector<long long> dp(m_nodes + 5, inf);

    dp[source] = 0;

    q.push({source, 0LL});

    while (!q.empty()) {
        int nod = q.top().nod;
        long long cost = q.top().cost;
        q.pop();

        if (cost > dp[nod]) continue;

        for (auto it: m_adjList[nod]) {
            long long z = cost + 1LL * it.second;
            if (z < dp[it.first]) {
                dp[it.first] = z;
                q.push({it.first, dp[it.first]});
            }
        }
    }

    return dp;
}

vector<int> Graph::bfs(int source) {
    deque<int> q;

    vector<int> distances(m_nodes + 5, -1);

    distances[source] = 0;

    q.push_back(source);


    while (!q.empty()) {
        int current = q.front();

        q.pop_front();

        for (auto it: m_adjList[current]) {
            if (distances[it.first] == -1) {
                distances[it.first] = 1 + distances[current];
                q.push_back(it.first);
            }
        }

    }


    return distances;

}

void Graph::dfs(int node) {
    m_visited[node] = 1;

    for (auto it: m_adjList[node]) {
        if (m_visited[it.first]) continue;
        dfs(it.first);
    }
}

bool Graph::HavelHakimi(vector<int> degSequence) {
    sort(degSequence.begin(), degSequence.end());
    reverse(degSequence.begin(), degSequence.end());

    int sz = (int) degSequence.size();

    for (int i = 0; i < sz; i++) {
        if (!degSequence[i]) break;
        for (int j = i + 1; j <= i + degSequence[i]; j++) {
            if (!degSequence[j]) return 0;
            if (j >= sz) return 0;

            degSequence[j]--;
        }


        int p = i + 1;
        int q = i + degSequence[i] + 1;

        vector<int> aux;
        while (p < i + degSequence[i] + 1 && q < sz) {
            if (degSequence[p] > degSequence[q])
                aux.push_back(degSequence[p]), p++;
            else
                aux.push_back(degSequence[q]), q++;
        }

        while (q < sz) aux.push_back(degSequence[q]), q++;
        while (p < i + degSequence[i] + 1) aux.push_back(degSequence[p]), p++;

        for (int j = i + 1; j < sz; j++)
            degSequence[j] = aux[j - i - 1];

        degSequence[i] = 0;
        //  for(auto it:degSequence)
        //     printf("%d ",it);
        // printf("\n");
    }


    return 1;
}

int Graph::getCC() {

    resetVisited();

    int ans = 0;
    for (int i = 1; i <= m_nodes; i++)
        if (!m_visited[i]) dfs(i), ans++;


    return ans;
}

vector <vector<int>> Graph::getSCCs() {
    vector <vector<int>> solution;
    vector<int> lvl(m_nodes + 5, 0);
    vector<int> low(m_nodes + 5, 0);
    vector<int> st;
    vector<bool> inStack(m_nodes + 5, 0);
    int currentLevel = 0;

    for (int i = 1; i <= m_nodes; i++)
        if (!lvl[i])
            tarjan(inStack, st, lvl, low, solution, i, 0, currentLevel);

    return solution;
}

vector <vector<int>> Graph::getBiconected() {
    vector <vector<int>> solution;
    vector<int> lvl(m_nodes + 5, 0);
    vector<int> low(m_nodes + 5, 0);
    vector<int> st;
    vector<bool> seen(m_nodes + 5, 0);
    vector<int> t(m_nodes + 5, 0);

    bicoDFS(t, solution, st, seen, lvl, low, 1, 0, 1);

    return solution;

}

vector <pair<int, int>> Graph::getCriticalEdges() {
    vector <vector<int>> solution;
    vector<int> lvl(m_nodes + 5, 0);
    vector<int> low(m_nodes + 5, 0);
    vector<int> st;
    vector<bool> seen(m_nodes + 5, 0);
    vector<int> t(m_nodes + 5, 0);

    bicoDFS(t, solution, st, seen, lvl, low, 1, 0, 1);

    vector <pair<int, int>> criticals;
    for (auto it: m_edges) {
        int x = it.first;
        int y = it.second.first;

        if (x == y) continue;

        if (lvl[x] < lvl[y]) continue;

        if (t[x] == y && low[x] > lvl[y])
            criticals.push_back(make_pair(x, y));
    }


    return criticals;
}

vector<int> Graph::getTopSort() {
    vector<int> solution;
    vector<bool> seen(m_nodes + 5, 0);

    for (int i = 1; i <= m_nodes; i++)
        if (!seen[i])
            topSort(solution, seen, i, 0);

    reverse(solution.begin(), solution.end());

    return solution;
}

pair<long long, vector<pair < int, int> > >

Graph::getMST() {
    sort(m_edges.begin(), m_edges.end(), cmp);
    vector <pair<int, int>> sol;

    DSU disjointSet(m_nodes);


    long long cost = 0;

    for (auto it: m_edges) {
        int x = it.first;
        int y = it.second.first;
        int z = it.second.second;

        int rx = disjointSet.getRoot(x);
        int ry = disjointSet.getRoot(y);

        if (rx != ry) {
            cost += 1LL * z;
            disjointSet.unite(rx, ry);
            sol.push_back(make_pair(x, y));
        }
    }


    return make_pair(cost, sol);

}

pair<int, vector<long long> > Graph::bellmanFord(int source) {
    deque<int> q;

    vector<bool> inQueue(m_nodes + 5, 0);
    vector<int> seen(m_nodes + 5, 0);


    q.push_back(source);
    inQueue[source] = seen[source] = 1;

    vector<long long> dp(m_nodes + 5, 1LL * INT_MAX);

    dp[source] = 0;

    while (!q.empty()) {
        int node = q.front();

        for (auto it: m_adjList[node]) {
            if (dp[it.first] < dp[node] + it.second) continue;

            dp[it.first] = dp[node] + it.second;
            if (!inQueue[it.first]) {
                q.push_back(it.first);
                inQueue[it.first] = 1;
            }

            seen[it.first]++;
            if (seen[it.first] == (m_nodes + 1))
                return make_pair(-1, dp);
        }

        inQueue[node] = 0;
        q.pop_front();
    }

    return make_pair(0, dp);


}

vector <vector<int>> Graph::royFloyd() {
    vector <vector<int>> m;

    m.resize(m_nodes + 5);
    for (int i = 0; i <= m_nodes; i++)
        m[i].resize(m_nodes + 5);

    for (auto it: m_edges) {
        int x = it.first;
        int y = it.second.first;
        m[x][y] = it.second.second;
    }

    for (int i = 1; i <= m_nodes; i++) {
        for (int j = 1; j <= m_nodes; j++) {
            if (i == j) continue;
            if (!m[i][j]) m[i][j] = inf;
        }
    }

    for (int k = 1; k <= m_nodes; k++) {
        for (int i = 1; i <= m_nodes; i++)
            for (int j = 1; j <= m_nodes; j++) {
                if (m[i][k] + m[k][j] < m[i][j]) m[i][j] = m[i][k] + m[k][j];
            }
    }

    return m;
}

vector<int> Graph::getDepths(int root) {
    vector<int> depths(m_nodes + 5, 0);
    depths[root] = 1;

    depthDFS(depths, root);


    return depths;

}

int Graph::getTreeDiam() {
    vector<int> depth = getDepths(1);

    int best = 1;
    for (int i = 1; i <= m_nodes; i++)
        if (depth[i] > depth[best]) best = i;

    depth = getDepths(best);

    for (int i = 1; i <= m_nodes; i++)
        if (depth[i] > depth[best]) best = i;

    return depth[best];
}

int Graph::getMaxFlow(vector <vector<int>> &c, int source, int destination) { /// flow-ul putea face parte din clasa
    vector <vector<int>> f;
    vector<int> tt;

    //  c.resize(m_nodes+5);
    f.resize(m_nodes + 5);

    tt.resize(m_nodes + 5);

    for (int i = 1; i <= m_nodes; i++) {
        f[i].resize(m_nodes + 5);
        // c[i].resize(m_nodes+5);
    }

    int sol = 0;

    while (bfs(f, c, tt, source, destination)) {

        for (auto it: m_adjList[destination]) {
            int x = it.first;
            int flow = c[x][destination] - f[x][destination];

            for (int i = x; i != source; i = tt[i])
                flow = min(flow, c[tt[i]][i] - f[tt[i]][i]);

            f[x][destination] += flow;
            f[destination][x] -= flow;

            for (int i = x; i != source; i = tt[i]) {
                f[tt[i]][i] += flow;
                f[i][tt[i]] -= flow;
            }

            sol += flow;
        }
    }

    return sol;
}


int main() {

    vector<vector<int>> solution;

    freopen("maxflow.in", "r", stdin);
    freopen("maxflow.out", "w", stdout);

    int n, m, x, y, z;

    scanf("%d%d", &n, &m);

    Graph G(n, 0, 0);

   /* vector <vector<int>> c;
    c.resize(n + 5);
    for (int i = 1; i <= n; i++)
        c[i].resize(n + 5);
    */
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &x, &y);
        G.addEdge(x, y);
        //G.addEdge(y, x);
    }

    solution = G.getSCCs();
    printf("%d\n", solution.size());
    for(int i = 0; i<solution.size(); ++i){
        for(int j = 0; j<solution[i].size(); ++j)
            printf("%d ", solution[i][j]);
        printf("\n");
    }

    return 0;


}