Cod sursa(job #1743610)

Utilizator GeanaVladGeana Vlad GeanaVlad Data 18 august 2016 14:18:35
Problema Componente tare conexe Scor 12
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int nr=1,viz[101],a[101][101],b[101][101],n,m,x,y,i,cnt,j,k;
vector<int>print,num;
void royfloyd()
{
    int k,i,j;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(a[i][k] && a[k][j]) a[i][j]=1;
}
void DFS(int x)
{
    int i;
    viz[x]=1;
    for(i=1;i<=n;i++)
    if(b[i][x] && !viz[i])
        {
            nr++;
            print.push_back(i);
            DFS(i);
        }

}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        a[x][y]=1;
    }
    royfloyd();
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    if(a[i][j]&&a[j][i]) b[i][j]=b[j][i]=1;
    for(i=1;i<=n;i++)
    if(!viz[i])
    {
        print.push_back(i);
        DFS(i);
        num.push_back(nr);
        cnt++;
    }
    g<<cnt<<'\n';
    for(i=0,j=1;i!=cnt;i++)
    {
        for(;j<=num[i];j++)
            g<<print[j]<<' ';
        g<<'\n';
    }

}