Pagini recente » Cod sursa (job #1439083) | Cod sursa (job #3205486) | Cod sursa (job #2368152) | Cod sursa (job #1270877) | Cod sursa (job #717641)
Cod sursa(job #717641)
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX_N 100001
int n,m,vizitat[MAX_N];
vector<int> g[MAX_N],gt[MAX_N],subgraf_max,st;
vector< vector<int> > solutie;
void citeste_graf(void)
{
freopen("ctc.in","r",stdin);
int i,x,y;
scanf("%d %d",&n,&m);
for(i=1; i<=m; i++)
{
scanf("%d %d",&x,&y);
g[x].push_back(y);
gt[y].push_back(x); //formez graful transpus
}
fclose(stdin);
}
void DF1(int nod)
{
vector<int> ::iterator i;
vizitat[nod]=1;
for(i=g[nod].begin(); i!=g[nod].end(); i++)
if(!vizitat[*i])
DF1(*i);
st.push_back(nod);
}
void DF2(int nod)
{
vector<int> ::iterator i;
vizitat[nod]=1;
for(i=gt[nod].begin(); i!=gt[nod].end(); i++)
if(!vizitat[*i])
DF2(*i);
subgraf_max.push_back(nod);
}
void sortare_topologica(void)
{
int i;
for(i=1; i<=n; i++)
if(!vizitat[i])
DF1(i);
reverse(st.begin(),st.end());
}
void componente_tare_conexe(void)
{
sortare_topologica();
vector<int> ::iterator i;
memset(vizitat,0,sizeof(vizitat));
for(i=st.begin(); i!=st.end(); i++)
if(!vizitat[*i])
{
DF2(*i);
solutie.push_back(subgraf_max);
subgraf_max.clear();
}
}
void afiseaza_solutie(void)
{
freopen("ctc.out","w",stdout);
vector< vector<int> > ::iterator i;
vector<int> ::iterator j;
printf("%d\n",solutie.size());
for(i=solutie.begin(); i!=solutie.end(); i++)
{
for(j=(*i).begin(); j!=(*i).end(); j++)
printf("%d ",*j);
printf("\n");
}
fclose(stdout);
}
int main()
{
citeste_graf();
componente_tare_conexe();
afiseaza_solutie();
return 0;
}