Cod sursa(job #2331573)

Utilizator gabiluciuLuciu Gabriel gabiluciu Data 29 ianuarie 2019 18:27:45
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.13 kb
/*
ID: gabriel100
LANG: C++
TASK:
*/
#include <cstdio>
#include <algorithm>
//#include <time.h>
#include <queue>
#include <cmath>
#include <stack>
#include <fstream>
#include <bitset>
#include <set>
#include <map>
#include <ctime>
#include <list>
#include <cstring>

#define nl '\n'
#define F first
#define S second
#define vi vector<int>
#define all(v) v.begin(),v.end()
#define eb(x) emplace_back(x)
#define ull unsigned long long
#define ll long long
#define ProblemName "ctc"
#define LocalName "data"
#ifdef INFOARENA
#define Filename ProblemName
#else
#define Filename LocalName
#endif
#define Input Filename".in"
#define Output Filename".out"
using namespace std;
ifstream cin(Input);
ofstream cout(Output);

template<class a, class type>
void print(a v, type t) {
    for_each(all(v), [](type x) { cout << x << ' '; });
    cout << nl;
}

struct nod {
    vi v1;
    vi v2; // invers
};
int n, m, x, y;
nod v[100001];

inline void add(const int &ind,const int &val) {
    v[ind].v1.emplace_back(val);
    v[val].v2.emplace_back(ind);
}

bitset<100001> viz;
stack<int> s;

inline void dfs(int i) {
    viz[i] = 1;
    for (auto it = v[i].v1.begin(); it != v[i].v1.end(); ++it) {
        if (!viz[*it]) {
            dfs(*it);
        }
    }
    s.push(i);
}
vector<int> vect;
inline void dfs_inv(int i) {
    viz[i] = 1;
    for (auto it = v[i].v2.begin(); it != v[i].v2.end(); ++it) {
        if (!viz[*it]) {
            dfs_inv(*it);
        }
    }
    vect.eb(i);
}

int main() {
    ios_base::sync_with_stdio(false);
    clock_t tStart = clock();
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> x >> y;
        add(x, y);
    }
    for (int i = 1; i <= n; ++i) {
        if (!viz[i]) {
            dfs(i);
        }
    }
    for(int i=0;i<=n;++i)viz[i] = 0;
    vector<vector<int> > ans;
    while (!s.empty()) {
        vect.clear();
        if (!viz[s.top()]) {
            dfs_inv(s.top());
            ans.eb(vect);
        }
        s.pop();
    }
    cout << ans.size() << nl;
    for(int i=0;i<ans.size();++i)
        print(ans[i],1234);
    cout.close();
    printf("\nTime taken: %.2fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
}