Cod sursa(job #1214583)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 30 iulie 2014 20:48:49
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <bitset>
#include <string.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <deque>

using namespace std;

const char infile[] = "ctc.in";
const char outfile[] = "ctc.out";

ifstream fin(infile);
ofstream fout(outfile);

const int MAXN = 100005;
const int oo = 0x3f3f3f3f;

typedef vector<int> :: iterator It;

const inline int min(const int &a, const int &b) { if( a > b ) return b;   return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b;   return a; }
const inline void Get_min(int &a, const int b)    { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b)    { if( a < b ) a = b; }

class Graph {
public:
    Graph() {

    }
    void build(int n) {
        this->n = n;
        adj.resize(n);
        index.resize(n);
        lowlink.resize(n);
        instack.resize(n);
        actIndex = 0;
    }
    void addEdge(int x, int y) {
        adj[x].push_back(y);
    }
    void Tarjan(int node) {
        lowlink[node] = index[node] = ++ actIndex;
        st.push(node);
        instack[node] = 1;
        for(It it = adj[node].begin(), fin = adj[node].end(); it != fin ; ++ it) {
            if(!index[*it]) {
                Tarjan(*it);
                lowlink[node] = min(lowlink[node], lowlink[*it]);
            } else if(instack[*it])
                lowlink[node] = min(lowlink[node], lowlink[*it]);
        }
        if(lowlink[node] == index[node]) {
            int nod;
            vector <int> act;
            do {
                nod = st.top();
                st.pop();
                instack[nod] = 0;
                act.push_back(nod);
            } while(nod != node);
            CTC.push_back(act);
        }
    }
    void makeCTC() {
        for(int i = 0 ; i < n ; ++ i)
            if(!index[i])
                Tarjan(i);
    }
    vector <vector <int> > getCTC() {
        makeCTC();
        return CTC;
    }
private:
    vector <vector <int > > adj;
    vector <vector <int> > CTC;
    vector <int> index;
    vector <int> lowlink;
    vector <bool> instack;
    stack <int> st;
    int actIndex;
    int n;

} G;

int n, m;


int main() {
    cin.sync_with_stdio(false);
    #ifndef ONLINE_JUDGE
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);
    #endif
    fin >> n >> m;
    G.build(n);
    for(int i = 1 ; i <= m ; ++ i) {
        int x, y;
        fin >> x >> y;
        -- x ; -- y;
        G.addEdge(x, y);
    }
    vector <vector <int> > ctc = G.getCTC();
    fout << ctc.size() << '\n';
    for(vector <vector <int> > :: iterator it = ctc.begin() ; it != ctc.end() ; ++ it, fout << '\n')
        for(vector <int> :: iterator i = it->begin() ; i != it->end() ; ++ i)
            fout << *i + 1 << ' ';
    fin.close();
    fout.close();
    return 0;
}