Pagini recente » Cod sursa (job #2795158) | Cod sursa (job #2068029) | Cod sursa (job #776574) | Cod sursa (job #3221870) | Cod sursa (job #1639534)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int nmax=100005;
int nr_comp,i,x,y,n,m,j,siz_comp;
stack <int> stiv;
vector <int> a[nmax]; /// graf normal
vector <int> b[nmax]; /// graf transpus
vector <int> ras[nmax];
bool viz[nmax],viz2[nmax],incomp[nmax];
void dfs_normal (int nod)
{
int h,vecini;
viz[nod]=1;
vecini=a[nod].size();
for (h=0;h<vecini;h++)
{
if (viz[a[nod][h]]==0)
dfs_normal(a[nod][h]);
}
stiv.push(nod);
}
void dfs_transpus (int nod)
{
int h,vecini;
viz2[nod]=1;
incomp[nod]=1;
vecini=b[nod].size();
for (h=0;h<vecini;h++)
{
if (viz2[b[nod][h]]==0)
dfs_transpus(b[nod][h]);
}
ras[nr_comp].push_back(nod);
}
int main()
{
f>>n>>m;
for (i=1;i<=m;i++)
{
f>>x>>y;
a[x].push_back(y);
b[y].push_back(x);
}
for (i=1;i<=n;i++)
if (viz[i]==0)
dfs_normal(i);
while (!stiv.empty())
{
if (incomp[stiv.top()]==0)
{
nr_comp++;
dfs_transpus(stiv.top());
}
stiv.pop();
}
g<<nr_comp<<'\n';
for (i=1;i<=nr_comp;i++)
{
siz_comp=ras[i].size();
for (j=0;j<siz_comp;j++)
g<<ras[i][j]<<" ";
g<<'\n';
}
return 0;
}