Cod sursa(job #2167175)

Utilizator mrhammerCiocan Cosmin mrhammer Data 13 martie 2018 20:31:11
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include<iostream>
#include<fstream>
#include<vector>
#define N_MAX 100000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector< int > mat[N_MAX];
vector< int > rev_mat[N_MAX];
vector< int > stk;
vector< vector<int> > sol;
bool viz[N_MAX];
bool viz2[N_MAX];
int n,m;
int strong_c;
void dfs(int node)
{
    viz[node] = true;
    for(int i=0;i<mat[node].size();i++)
    {
        if(viz[ mat[node][i] ] == false) dfs(mat[node][i]);
    }
    stk.push_back(node);
}
void dfs2(int node)
{
    viz2[node] = true;
    sol[strong_c-1].push_back(node+1);
    for(int i=0;i<rev_mat[node].size();i++)
    {
        if(viz2[ rev_mat[node][i] ] == false) dfs2(rev_mat[node][i]);
    }
}
void kosaraju()
{
    for(int i=0;i<n;i++)
    {
        if(viz[i] == false) dfs(i);
    }
    while(stk.size()>0)
    {
        int x = stk[stk.size()-1];
        stk.pop_back();
        if(viz2[x] == false)
        {
            strong_c++;
            vector<int> z;
            sol.push_back(z);
            dfs2(x);
        }
    }
}
int main()
{
    strong_c = 0;
    fin>>n>>m;
    int k1,k2;
    for(int i=0;i<m;i++)
    {
        fin>>k1>>k2;
        mat[k1-1].push_back(k2-1);
        rev_mat[k2-1].push_back(k1-1);
    }
    kosaraju();
    fout<<strong_c<<"\n";
    for(int i=0;i<sol.size();i++)
    {
        for(int j=0;j<sol[i].size();j++)
        {
            fout<<sol[i][j]<<" ";
        }
        fout<<"\n";
    }
}