Pagini recente » Cod sursa (job #1851791) | Cod sursa (job #2486516) | Cod sursa (job #1587825) | Cod sursa (job #1762339) | Cod sursa (job #1374265)
#include <fstream>
#define nMax 101
using namespace std;
ifstream x ("ctc.in");
ofstream y ("ctc.out");
struct node
{
int data;
node *next;
};
struct struct2
{
int v;
int ft;
};
bool visited[nMax];
int n,time,k;
int scc[nMax];
struct2 t[nMax];
node *head[nMax],*rhead[nMax];
node *tail[nMax],*rtail[nMax];
void add_graph(int A, int B)
{
if(!head[A])
{
head[A]=new node();
head[A]->data=B;
head[A]->next=NULL;
tail[A]=head[A];
}
else
{
node *temp;
temp=new node();
temp->data=B;
temp->next=NULL;
tail[A]->next=temp;
tail[A]=temp;
}
}
void add_rgraph(int A, int B)
{
if(!rhead[A])
{
rhead[A]=new node();
rhead[A]->data=B;
rhead[A]->next=NULL;
rtail[A]=rhead[A];
}
else
{
node *temp;
temp=new node();
temp->data=B;
temp->next=NULL;
rtail[A]->next=temp;
rtail[A]=temp;
}
}
void dfs_graph(int i)
{
node *temp;
temp=head[i];
visited[i]=true;
while(temp)
{
if(!visited[temp->data])
dfs_graph(temp->data);
temp=temp->next;
}
t[i].ft=++time;
}
void dfs_rgraph(int i)
{
node *temp;
temp=rhead[i];
scc[i]=k;
visited[i]=true;
while(temp)
{
if(!visited[temp->data])
dfs_rgraph(temp->data);
temp=temp->next;
}
}
void sort()
{
int i,j;
struct2 aux;
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
if(t[i].ft<t[j].ft)
{
aux=t[i];
t[i]=t[j];
t[j]=aux;
}
}
void show(int j)
{
int i;
node *temp;
for(i=1;i<=n;i++)
{
y<<i<<" --> ";
if(j==0)
temp=head[i];
else
temp=rhead[i];
while(temp)
{
y<<temp->data<<' ';
temp=temp->next;
}
y<<'\n';
}
y<<'\n';
}
int main()
{
int i;
int m;
x>>n>>m;
int A,B;
while(x>>A && x>>B)
{
add_graph(A,B);
add_rgraph(B,A);
}
//show(0);
//show(1);
for(i=1;i<=n;i++)
t[i].v=i;
for(i=1;i<=n;i++)
if(!t[i].ft)
{
dfs_graph(i);
}
sort();
/*
for(i=1;i<=n;i++)
y<<i<<' ';
y<<'\n';
*/
/*
for(i=1;i<=n;i++)
y<<t[i].v<<' ';
y<<'\n';
for(i=1;i<=n;i++)
y<<t[i].ft<<' ';
y<<'\n';
y<<'\n';
*/
for(i=1;i<=n;i++)
visited[i]=false;
for(i=1;i<=n;i++)
if(!visited[t[i].v])
{
k++;
dfs_rgraph(t[i].v);
}
y<<k<<'\n';
for(i=1;i<=k;i++)
{
for(int j=1;j<=n;j++)
if(scc[j]==i)
y<<j<<' ';
y<<'\n';
}
/*
for(i=1;i<=n;i++)
y<<scc[i]<<' ';
y<<'\n';
*/
return 0;
}