Cod sursa(job #2047486)

Utilizator Tataru_AdelinTataru Adelin Tataru_Adelin Data 24 octombrie 2017 21:27:34
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");


class punct
{
public:
    int index=0;
    int lowlink=0;
};

vector<vector<int>> ans;
int nr;
void dfs(int nod,vector<vector<int>>& path,vector<punct>& v,bitset<100010>& s,stack<int>& S)
{
    v[nod].index=v[nod].lowlink=++nr;
    S.push(nod);
    s[nod]=1;
    for(int i=0;i<path[nod].size();i++)
    {
        if(!v[path[nod][i]].index)
        {
            dfs(path[nod][i],path,v,s,S);
            v[nod].lowlink=min(v[nod].lowlink,v[path[nod][i]].lowlink);
        }
        else if(s[path[nod][i]])
            v[nod].lowlink=min(v[nod].lowlink,v[path[nod][i]].lowlink);
    }
    if(v[nod].index!=v[nod].lowlink)
        return;
    vector<int> c;

    for(;;)
    {
        c.push_back(S.top());
        s[S.top()]=0;
        if(v[S.top()].index==v[S.top()].lowlink)
        {
            S.pop();
            break;
        }
        S.pop();
    }
    ans.push_back(c);
}


int main()
{
    int nodes, edges, x, y;
    fin>>nodes>>edges;
    vector<vector<int>> path(nodes+5);
    vector<punct> v(nodes+5);
    bitset<100010> s;
    stack<int> S;

    for(;edges;edges--)
    {
        fin>>x>>y;
        path[x].push_back(y);
    }
    for(int i=1;i<=nodes;i++)
    {
        if(!v[i].index)
            dfs(i,path,v,s,S);
    }


    fout<<ans.size()<<'\n';

    for(int i=0;i<ans.size();i++)
    {
        for(int j=0;j<ans[i].size();j++)
            fout<<ans[i][j]<<' ';
        fout<<'\n';
    }
    return 0;
}