Cod sursa(job #3373836)

Utilizator ThoughtfulScholarCalin Andrei Razvan ThoughtfulScholar Data 7 noiembrie 2026 22:48:58
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 7.12 kb



/*
//Dep
#include <cstdio>
#include <vector>
#include <algorithm>

#define MOD 666013

#define MAXN 256

std::vector <int> g1[MAXN+1], g2[MAXN+1], v1[MAXN+1], v2[MAXN+1];

int ans;

int u, w, k, r[MAXN+1], s[MAXN+1], c[MAXN+1], best[MAXN+1], h[MAXN+1], t[MAXN+1];
bool e[MAXN+1], viz[MAXN+1], m1[MAXN+1][MAXN+1], m2[MAXN+1][MAXN+1];
int dp[MAXN+1][MAXN+1], aux[MAXN+1];

void dfs1(int x){
    viz[x]=1;
    for(auto y:g1[x])
        if(viz[y]==0)
            dfs1(y);
    r[++u]=x;
}

void dfs2(int x){
    viz[x]=0;
    s[k]++;
    c[x]=k;
    for(auto y:g2[x])
        if(viz[y]==1)
            dfs2(y);
}

void dfs3(int x){
    viz[x]=1;

    dp[x][s[x]]=1;

    for(auto y:v1[x]){
        if(viz[y]==0){
            h[y]=h[x]+1;
            t[y]=x;
            dfs3(y);
            for(int i=0; i<=w; i++){
                aux[i]=dp[x][i];
                dp[x][i]=0;
            }

            for(int i=0; i<=w; i++)
                for(int j=0; i+j<=w; j++)
                    dp[x][i+j]=(dp[x][i+j]+1LL*aux[i]*dp[y][j])%MOD;
        }
    }

    dp[x][0]=1;
}

int main(){
    FILE *fin, *fout;
    fin=fopen("dep.in", "r");
    fout=fopen("dep.out", "w");

    int n, m;
    fscanf(fin, "%d%d%d", &n, &m, &w);

    for(int i=1; i<=m; i++){
        int x, y;
        fscanf(fin, "%d%d", &x, &y);

        g1[y].push_back(x);
        g2[x].push_back(y);
    }

    for(int i=1; i<=n; i++)
        if(viz[i]==0)
            dfs1(i);

    for(int i=n; i>0; i--){
        if(viz[r[i]]==1){
            k++;
            dfs2(r[i]);
        }
    }

    for(int i=1; i<=n; i++){
        m1[c[i]][c[i]]=1;
        for(auto x:g1[i]){
            if(m1[c[i]][c[x]]==0){
                m1[c[i]][c[x]]=1;
                v1[c[i]].push_back(c[x]);
            }
        }

        m2[c[i]][c[i]]=1;
        for(auto x:g2[i]){
            if(m2[c[i]][c[x]]==0){
                m2[c[i]][c[x]]=1;
                v2[c[i]].push_back(c[x]);
            }
        }
    }

    for(int i=1; i<=k; i++)
        std::sort(v1[i].begin(), v1[i].end());

    for(int i=1; i<=k; i++){
        if(viz[i]==0){
            dfs3(i);
            v1[0].push_back(i);
        }
    }

    int x=0;

    dp[0][0]=1;
    for(auto y:v1[0]){
        for(int i=0; i<=w; i++){
            aux[i]=dp[x][i];
            dp[x][i]=0;
        }
        for(int i=0; i<=w; i++)
            for(int j=0; i+j<=w; j++)
                dp[x][i+j]=(dp[x][i+j]+1LL*aux[i]*dp[y][j])%MOD;
    }

    fprintf(fout, "%d\n", dp[0][w]);

    fclose(fin);
    fclose(fout);
    return 0;
}
*/



//Pamant
/*
#include <fstream>

using namespace std;

ifstream f("pamant.in");
ofstream g("pamant.out");

int n,m,L[400004],urm[400004],vec[400004],k,nr,cc[100004],low[100004],lev[100004],np,rad,nf[100004];
bool viz[100004],pa[100004];

void Add(int x1, int x2)
{
    urm[++k]=L[x1];
    vec[k]=x2;
    L[x1]=k;
}

void DFS(int nc, int t)
{
    int z,nn;
    viz[nc]=1;
    lev[nc]=lev[t]+1;
    low[nc]=lev[nc];
    z=L[nc];
    while (z)
    {
        nn=vec[z];
        if (nn!=t)
        {
            if (!viz[nn])
            {
                nf[nc]++;
                DFS(nn,nc);
                low[nc]=min(low[nc],low[nn]);
                if (low[nn]>=lev[nc] and nc!=rad)
                    pa[nc]=1;
            }
            else
                low[nc]=min(low[nc],lev[nn]);
        }
        z=urm[z];
    }
}

int main()
{
    int i,x1,x2;
    f >> n >> m;
    for (i=1;i<=m;i++)
    {
        f >> x1 >> x2;
        Add(x1,x2);
        Add(x2,x1);
    }
    for (i=1;i<=n;i++)
        if (!viz[i])
        {
            rad=i;
            DFS(i,0);
            if (nf[i]>=2)
                pa[i]=1;
            cc[++nr]=i;
        }
    for (i=1;i<=n;i++)
        np+=pa[i];
    g << nr << '\n';
    for (i=1;i<=nr;i++)
        g << cc[i] << ' ';
    g << '\n' << np << '\n';
    for (i=1;i<=n;i++)
        if (pa[i])
            g << i << ' ';
    return 0;
}
*/


//Ctc
/*
#include <iostream>
#include <vector>
#include <fstream>
#define NMAX 100001

using namespace std;

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

int n, nr, nrc;

//graful initial prin liste de adiacenta
 vector<int> G[NMAX];

//graful transpus
 vector<int> GT[NMAX];

 int post[NMAX];
 bool viz[NMAX];

 vector<int> ctc[NMAX]; //contine vf din comp tare conexa i

 void DFS(int x);
 void DFST(int x);

 void citire();
 void afisare();

 void citire()
 {
    int m, i, x, y;
    fin >> n >> m;
    for(int i=0; i<m; i++)
    {
        fin >> x >> y;
        //exista arc de la x la y in G
        G[x].push_back(y);
        //exista arc de la y la x in GT
        GT[y].push_back(x);
    }
 }

 void afisare()
 {
     fout << nrc << " " << endl;
     for(int i=1; i<=nrc; i++)
     //afisaz vf din comp tacre conexa i
     {
         for(int j=0; j<ctc[i].size(); j++)
            fout << ctc[i][j] << " ";
            fout << endl;
     }
        fout << endl;
 }

 void DFS(int x)
 {
     int i;
     viz[x]=1;
     for(i=0; i<G[x].size(); i++)
        if(!viz[G[x][i]])
            DFS(G[x][i]);
    post[++nr]=x;
 }

  void DFST(int x)
 {
     int i;
     viz[x]=0;
     ctc[nrc].push_back(x);
     for(i=0; i<GT[x].size(); i++)
        if(viz[GT[x][i]])
            DFST(GT[x][i]);
 }

int main()
{
    citire();
    for(int i=1; i<=n; i++)
        if(!viz[i])
        DFS(i);
    //parcurg vec post de la dr la st
    for(int i=n; i>0; i--)
        if(viz[post[i]]==1) //post de i nevizitat in GT
            {
                //am identificat o comp noua tare conexa
                nrc++;
                DFST(post[i]);
            }
    afisare();
    return 0;
}
*/


//Biconex
///sortaret
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int i,f[100010],ft[100010],cn,n,m,x,y,p;
vector <int> v[100010],vt[100010];
stack <int> q;
queue <int> ras[100010];
void dfs(int k)
{
    for(auto it : v[k])
    {
        if(f[it]==0)
        {
            f[it]=1;
            dfs(it);
        }
    }
    q.push(k);
}

void dfst(int k)
{
    for(auto it : vt[k])
    {
        if(ft[it]==0)
        {
            ft[it]=cn;
            ras[cn].push(it);
            dfst(it);
        }
    }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        vt[y].push_back(x);
    }
    for(i=1; i<=n; i++)
        if(f[i]==0)
        {
            f[i]=1;
            dfs(i);
        }
    while(q.size())
    {
        p=q.top();
        q.pop();
        if(ft[p]==0)
        {
            cn++;
            ras[cn].push(p);
            ft[p]=cn;
            dfst(p);
        }
    }
    fout<<cn<<'\n';
    for(i=1; i<=cn; i++)
    {
        while(ras[i].size())
        {
            fout<<ras[i].front()<<" ";
            ras[i].pop();
        }
        fout<<'\n';
    }
    return 0;
}