Pagini recente » Cod sursa (job #2033831) | Cod sursa (job #2044470) | Cod sursa (job #2037474) | Cod sursa (job #1059876) | Cod sursa (job #952368)
Cod sursa(job #952368)
//
// ctc.cpp
// Componente Tare Conexe
//
// Created by Andrei Constantinescu on 23.05.2013.
// Copyright (c) 2013 Andrei Constantinescu. All rights reserved.
//
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
#define NMAX 100
int n,m;
vector <int> grf[NMAX],grft[NMAX],con[NMAX];
int st[NMAX],k=0,nrcon;
bool viz[NMAX];
void df(int nod) {
viz[nod]=1;
for(int i=0;i<grf[nod].size();i++)
if(!viz[grf[nod][i]]) df(grf[nod][i]);
st[k]=nod;
k++;
}
void dft(int nod) {
viz[nod]=0;
con[nrcon].push_back(nod);
for(int i=0;i<grft[nod].size();i++)
if(viz[grft[nod][i]]) dft(grft[nod][i]);
}
int main() {
f>>n>>m;
for(int i=1; i<=m; i++) {
int a, b;
f>>a>>b;
grf[a].push_back(b);
grft[b].push_back(a);
}
for(int i=1;i<=n;i++)
if(!viz[i]) df(i);
nrcon=0;
for(int i=n-1;i>=0;i--)
if(viz[st[i]]) {
dft(st[i]);
nrcon++;
}
g<<nrcon;
g<<"\n";
for(int i=0;i<nrcon;i++) {
for(int j=0;j<con[i].size();j++)
g<<con[i][j]<<" ";
g<<"\n";
}
}