Pagini recente » Cod sursa (job #361245) | Cod sursa (job #1584066) | Cod sursa (job #385787) | Cod sursa (job #203085) | Cod sursa (job #707953)
Cod sursa(job #707953)
#include <fstream>
#include <vector>
#define nmax 200000
using namespace std;
vector <int> pre[nmax],suc[nmax];
int prev[nmax],sucv[nmax];
int viz[nmax];
int n,m;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector <int> stiv[nmax];
void dfsp(int a,int ma)
{
prev[a]=ma;
vector <int>::iterator it;
for(it=pre[a].begin();it!=pre[a].end();it++)
{
if(prev[*it]==0)
{
dfsp(*it,ma);
}
}
}
void dfss(int a,int ma)
{
sucv[a]=ma;
vector <int>::iterator it;
for(it=suc[a].begin();it!=suc[a].end();it++)
{
if(sucv[*it]==0)
{
dfss(*it,ma);
}
}
}
void citire()
{
int i,j,k;
in>>n>>m;
for(i=1;i<=m;i++)
{
in>>j>>k;
suc[j].push_back(k);
pre[k].push_back(j);
}
}
int main()
{
int ma=0,i,j;
citire();
for(i=1;i<=n;i++)
{
if(prev[i]==0)
{
ma++;
dfsp(i,ma);
dfss(i,ma);
for(j=1;j<=n;j++)
if(prev[j]!=sucv[j])
{
prev[j]=0;
sucv[j]=0;
}
else
if(ma==prev[j])
stiv[ma].push_back(j);
}
}
vector<int>::iterator it;
out<<ma;
for(i=1;i<=ma;i++)
{
out<<"\n";
for(it=stiv[i].begin();it!=stiv[i].end();it++)
{
out<<*it<<" ";
}
}
}