Cod sursa(job #2118141)

Utilizator serjiuuAvacaritei Sergiu serjiuu Data 30 ianuarie 2018 09:55:23
Problema Componente tare conexe Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <list>
#include <bitset>

using namespace std;

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

const int nmax=23000;

int n, m, K;
int a[nmax], b[nmax], ans[nmax][nmax];

list <int> g[nmax], gt[nmax];
bitset <nmax> vis, VIS;

void read_data()
{
    int i, x, y;

    fin>>n>>m;

    for(i=1;i<=m;i++)
    {
        fin>>x>>y;

        g[x].push_back(y);
        gt[y].push_back(x);
    }
}
inline void dfs(int node,int root)
{
    list <int> :: iterator it;

    //fout<<node<<' ';

    vis[node]=true;
    a[node]=root;

    for(it=g[node].begin();it!=g[node].end();it++)
        if(!vis[*it])
            dfs(*it,root);
}
inline void DFS(int node,int root)
{
    list <int> :: iterator it;

    //fout<<node<<' ';

    vis[node]=true;
    b[node]=root;

    for(it=gt[node].begin();it!=gt[node].end();it++)
        if(!vis[*it])
            DFS(*it,root);
}
void solve()
{
    int i, j, k;

    for(i=1;i<=n;i++)
    {
        if(!VIS[i])
        {
            K++;
            dfs(i,i);
            vis.reset();
            DFS(i,i);
            vis.reset();
            k=0;
            for(j=1;j<=n;j++)
                if(a[j]==b[j] && a[j] && b[j])
                    VIS[j]=true,ans[K][++k]=j;
        }
    }
}
void print()
{
    int i, j;

    fout<<K<<'\n';

    for(i=1;i<=K;i++)
    {
        for(j=1;ans[i][j];j++)
            fout<<ans[i][j]<<' ';
        fout<<'\n';
    }
}
int main()
{
    read_data();
    solve();
    print();

    return 0;
}