Cod sursa(job #2510299)

Utilizator YetoAdrian Tonica Yeto Data 16 decembrie 2019 11:44:06
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
int n, m, i, j, a, b, nrc, x, y;
int viz[100001], low[100001];
vector <int> cc[100001];
bool s[100001];
vector <int> g[100001];
stack <int> st;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int niv;
void dfs (int nod)
{
    niv++;
    viz[nod]=niv;
    low[nod]=niv;
    st.push(nod);
    s[nod]=1;
    for (int i=0;i<g[nod].size();i++) {
        int fiu = g[nod][i];
        if (viz[fiu]==0) {
            dfs(fiu);
            low[nod]=min(low[nod], low[fiu]);
        }
        else if (s[fiu]==1)
            low[nod]=min(low[nod], viz[fiu]);
    }
    if (low[nod]==viz[nod]) {
        nrc++;
        x=nod;
        do{
            y=st.top();
            s[y]=0;
            cc[nrc].push_back(y);
            st.pop();
        }while(y!=x);
    }
}

int main () {
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>a>>b;
        g[a].push_back(b);
    }
    for (i=1;i<=n;i++) {
        if (viz[i]==0){
                niv=1;
            dfs(i);
        }
    }
    fout<<nrc<<"\n";
    for (i=1;i<=nrc;i++) {
        for (j=0;j<cc[i].size();j++)
            fout<<cc[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}