Pagini recente » Cod sursa (job #1752015) | Cod sursa (job #2735859) | Cod sursa (job #2947497) | Cod sursa (job #1930315) | Cod sursa (job #2526815)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
vector <int> A[100001];
vector <int> T[100001];
vector <int> C[100001];
int n,m;
int VIZ[100001];
stack <int> s;
int nrc;
void df(int v)
{
vector <int> :: iterator it;
VIZ[v]=1;
for (it=A[v].begin();it!=A[v].end();it++)
{
int w;
w=(*it);
if (VIZ[w]==0)
df(w);
}
s.push(v);
}
void dft(int v)
{
vector <int> :: iterator it;
VIZ[v]=1;
C[nrc].push_back(v);
for (it=T[v].begin();it!=T[v].end();it++)
{
int w;
w=(*it);
if (VIZ[w]==0)
dft(w);
}
}
int main()
{
fi>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
fi>>a>>b;
A[a].push_back(b);
T[b].push_back(a);
}
/// algoritmul Kosaraju-Sharir
/// se depun varfurile grafului in s, dupa finishing time
for (int i=1;i<=n;i++)
if (VIZ[i]==0)
df(i);
/// se fac traversari df in graful transpus
/// considerand varfurile in ordinea extragerii din s
for (int i=1;i<=n;i++)
VIZ[i]=0;
nrc=0;
while (!s.empty())
{
int v;
v=s.top();
s.pop();
if (VIZ[v]==0)
{
nrc++;
dft(v);
}
}
fo<<nrc<<"\n";
for (int i=1;i<=nrc;i++)
{
vector <int> :: iterator it;
for (it=C[i].begin();it!=C[i].end();it++)
fo<<(*it)<<" ";
fo<<"\n";
}
fi.close();
fo.close();
return 0;
}