Pagini recente » Cod sursa (job #1340645) | Cod sursa (job #304192) | Cod sursa (job #1381351) | Cod sursa (job #52268) | Cod sursa (job #2279485)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
int N,M;
vector <int> ADJ[100001];
vector <int> ADJT[100001];
vector <int> CTC[100001];
int VIZ[100001];
stack <int> S;
stack <int> SS;
int rez=0;
void df(int v)
{
vector <int> :: iterator it;
VIZ[v]=1;
for (it=ADJ[v].begin();it!=ADJ[v].end();it++)
{
int varf;
varf=(*it);
if (VIZ[varf]==0)
df(varf);
}
S.push(v);
}
void dft(int v)
{
vector <int> :: iterator it;
VIZ[v]=1;
CTC[rez].push_back(v);
for (it=ADJT[v].begin();it!=ADJT[v].end();it++)
{
int varf;
varf=(*it);
if (VIZ[varf]==0)
dft(varf);
}
}
int main()
{
fi>>N>>M;
for (int i=1;i<=M;i++)
{
int a,b;
fi>>a>>b;
ADJ[a].push_back(b);
ADJT[b].push_back(a);
}
/// se depun varfuri in stiva
for (int i=1;i<=N;i++)
if (VIZ[i]==0)
df(i);
/// se face df in graful transpus
/// varfurile sunt considerate in ordinea data de stiva S
for (int i=1;i<=N;i++)
VIZ[i]=0;
/// numarul de componente tare conexe
SS=S;
while (!S.empty())
{
int v;
v=S.top();
S.pop();
if (VIZ[v]==0)
{
rez++;
dft(v);
}
}
fo<<rez<<'\n';
for(int nrsol=1;nrsol<=rez;++nrsol)
{
for(auto nod:CTC[nrsol])fo<<nod<<" ";
fo<<'\n';
}
fi.close();
fo.close();
return 0;
}