Pagini recente » Cod sursa (job #1099024) | Cod sursa (job #2941154) | Cod sursa (job #2516461) | Cod sursa (job #1060591) | Cod sursa (job #936164)
Cod sursa(job #936164)
#include<fstream>
#include<vector>
#include<stack>
#define lmax 110000
using namespace std;
vector<int>v1[lmax];
vector<int>v2[lmax];
vector<int>v[lmax];
int k;
int parcurs1[lmax];
int parcurs2[lmax];
stack<int>s;
ofstream g("ctc.out");
void df1(int a)
{
int i;
parcurs1[a]=1;
for(i=0;i<v1[a].size();i++)
{
if(parcurs1[v1[a][i]]==0)df1(v1[a][i]);
}
s.push(a);
}
void df2(int a)
{ v[k].push_back(a);
parcurs2[a]=1;
int i;
for(i=0;i<v2[a].size();i++)
{
if(parcurs2[v2[a][i]]==0)
df2(v2[a][i]);
}
}
main()
{
int n,m,a,b,i,j;
ifstream f("ctc.in");
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>a>>b;
v1[a].push_back(b);
v2[b].push_back(a);
}
for(i=1;i<=n;i++)
if(parcurs1[i]==0)df1(i);
while(!s.empty())
{
if(parcurs2[s.top()]==0)
{
k++;
df2(s.top());
}
s.pop();
}
g<<k<<"\n";
for(i=1;i<=k;i++)
{
for(j=0;j<v[i].size();j++)
g<<v[i][j]<<" ";
g<<"\n";
}
}