Cod sursa(job #2159531)

Utilizator OpportunityVlad Negura Opportunity Data 10 martie 2018 23:45:17
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 3.4 kb
#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(false);cout.precision(30);cout.tie(0);cin.tie(0);
#define ll long long
#define ld long double
#define rep(i, a, b) for(__typeof(b)i=(a)-((a)>(b));i!=(b)-((a)>(b));i+=1-2*((a)>(b)))
#define whilet() ll t;cin>>t;while(t--)
#define all(c) (c).begin(), (c).end()

vector <int> adj[100001], con, idx, lowlink, in_stack;
vector < vector <int> > C;
stack <int> S;

int indecs;

void read_in(vector <int>* adj, int& n)
{
    ifstream in("ctc.in");
    int cnt_edges, x, y;

    in >> n;
    for (in >> cnt_edges; cnt_edges > 0; -- cnt_edges)
        in >> x >> y,
                adj[x - 1].push_back(y - 1);
    in.close();
}

void print_out(const vector < vector <int> >& G)
{
    ofstream out("ctc.out");

    out << G.size() << endl;
    for (auto x:G) {
        for (auto y:x)
            out << y + 1 << ' ';
        out << endl;
    }
    out.close();
}

void tarjan(const int n, const vector <int>* adj)
{
    idx[n] = lowlink[n] = indecs;
    indecs ++;
    S.push(n), in_stack[n] = 1;

    vector <int>::const_iterator it;
    for (it = adj[n].begin(); it != adj[n].end(); ++ it) {
        if (idx[*it] == -1)
            tarjan(*it, adj),
                    lowlink[n] = min(lowlink[n], lowlink[*it]);
        else if (in_stack[*it])
            lowlink[n] = min(lowlink[n], lowlink[*it]);
    }
    if (idx[n] == lowlink[n]) {
        con.clear();
        int node;
        do {
            con.push_back(node = S.top());
            S.pop(), in_stack[node] = 0;
        }
        while (node != n);
        C.push_back(con);
    }
}

int main(void)
{
    int n;
    read_in(adj, n);

    idx.resize(n), lowlink.resize(n), in_stack.resize(n);
    idx.assign(n, -1), in_stack.assign(n, 0);
    for (int i = 0; i < n; ++ i) if (idx[i] == -1)
            tarjan(i, adj);

    print_out(C);

    return 0;
}
//#include <bits/stdc++.h>
//using namespace std;
//#define _ ios_base::sync_with_stdio(false);cout.precision(30);cout.tie(0);cin.tie(0);
//#define ll long long
//#define ld long double
//#define rep(i, a, b) for(__typeof(b)i=(a)-((a)>(b));i!=(b)-((a)>(b));i+=1-2*((a)>(b)))
//#define whilet() ll t;cin>>t;while(t--)
//#define all(c) (c).begin(), (c).end()
//
//ifstream fi("ctc.in");
//ofstream fo("ctc.out");
//
//int n,m,x,y,idxc;
//vector<int> idx, in, low, g[100001];
//vector<vector<int>> scc;
//stack<int> s;
//
//void tarjan(const int v) {
//    idx[v] = low[v] = idxc;
//    idxc++;
//    s.push(v);
//    in[v] = 1;
//
//    for (auto &u:g[v]) {
//        if (idx[u] == -1){
//            tarjan(u);
//            low[v] = min(low[v], low[u]);
//        } else if (in[u]) {
//            low[v] = min(low[v], idx[u]);
//        }
//    }
//
//    vector<int> comp;
//    if (low[v] == idx[v]) {
//        int u;
//        do {
//            u = s.top();
//            in[u] = 0;
//            s.pop();
//            comp.push_back(u);
//        } while(u != v);
//        scc.push_back(comp);
//    }
//}
//
//
//int main() {_
//    fi >> n >> m;
//    in.resize(n);
//    low.resize(n);
//    idx.resize(n);
//    in.assign(n,0);
//    idx.assign(n,-1);
//
//    rep(i,0,m) {
//        fi >> x >> y;
//        g[x-1].push_back(y-1);
//    }
//
//    rep(i,0,n) {
//        if (idx[i] == -1) tarjan(i);
//    }
//
//    fo << scc.size() << endl;
//    rep(i,0,scc.size()) {
//        rep(j,0,scc[i].size()) fo << scc[i][j]+1 << ' ';
//        fo << endl;
//    }
//
//    return 0;
//}