Pagini recente » Cod sursa (job #109560) | Cod sursa (job #2871044) | Cod sursa (job #679072) | Cod sursa (job #914195) | Cod sursa (job #679517)
Cod sursa(job #679517)
#include <fstream>
#include <string>
#include <sstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
typedef struct Nod {
int inf;
struct Nod *next;
} NOD;
typedef struct {
NOD *prim;
} LIST;
#define NMAX 100010
LIST G[NMAX], GT[NMAX];
int N, M;
int Plus[NMAX];
int Minus[NMAX];
int b[NMAX];
void insereaza(LIST *L, int x)
{
NOD* q=new(NOD);
q->inf = x;
q->next = L->prim;
L->prim = q;
}
void afis(LIST *L)
{
for(NOD* q=L->prim; q; q=q->next){
g << q->inf << ' ';
}
g << '\n';
}
void dfs(LIST G[],int x,int a[],int p)
{
a[x] = p;
for (NOD *q=G[x].prim; q; q=q->next){
if (a[q->inf]!=p){
dfs(G,q->inf,a,p);
}
}
}
void compTareConexe()
{
stringstream ss;
string s;
int i, j, nr=0;
for (i=1; i<=N; i++){
if(!b[i]){
nr++;
dfs(G,i,Plus,nr);
dfs(GT,i,Minus,nr);
for (j=1; j<=N; j++){
if (Plus[j]==nr && Minus[j]==nr){
ss << j << ' ';
b[j] = nr;
}
}
ss << '\n';
}
}
g << nr << '\n';
g << ss.str();
}
int main()
{
int i, x, y;
f >> N >> M;
for (i=0; i<M; i++){
f >> x >> y;
insereaza(&G[x],y);
insereaza(>[y],x);
}
//afis(>[3]);
compTareConexe();
return 0;
}