Pagini recente » Cod sursa (job #2043958) | Cod sursa (job #888345) | Cod sursa (job #447509) | Monitorul de evaluare | Cod sursa (job #2562748)
#include <bits/stdc++.h>
#define nmax 100005
#define pb push_back
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, indexat, depth[nmax], st[nmax], ss, numscc;
vector <int> graph[nmax];
vector <int> ctc[nmax];
bitset <nmax> vizat;
int strongcon(int v, int indexat)
{
depth[v] = indexat;
st[ss++] = v;
vizat[v] = 1;
unsigned i, len;
len = graph[v].size();
int vecin;
for(i = 0; i < len; i++)
{
vecin = graph[v][i];
if(depth[vecin] == 0)
depth[v] = min(depth[v], strongcon(vecin, indexat + 1));
else if(vizat[vecin])
depth[v] = min(depth[v], depth[vecin]);
}
if(depth[v] == indexat)
{
do{
vecin = st[--ss];
vizat[vecin] = false;
ctc[numscc].pb(vecin);
}while(vecin != v);
numscc++;
}
return depth[v];
}
int main()
{
int i, x, y;
fin >> n >> m;
for(i = 0; i < m; i++)
fin >> x >> y, graph[x].pb(y);
for(i = 1; i <= n; i++)
if(depth[i] == 0)
strongcon(i, 1);
fout << numscc << '\n';
for(i = 0; i < numscc; i++)
{
x = ctc[i].size();
for(y = x - 1; y >= 0; y--)
fout << ctc[i][y] << ' ';
fout << '\n';
}
return 0;
}
/*
Mirela_Magdalena
Catrina Mirela
#define NMAX 100005
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int index = 1;
int n, m, nrc;
int isInStack[NMAX], viz[NMAX], lowlink[NMAX], idx[NMAX];
vector<int> graph[NMAX];
vector<int> CC[NMAX];
stack<int> S;
void read()
{
int x, y;
f>>n>>m;
for(int i = 0; i < m; ++i)
{
f>>x>>y;
graph[x].push_back(y);
}
}
void addCC()
{
nrc++;
int top;
do{
top = S.top();
CC[nrc].push_back(top);
S.pop();
isInStack[top] = 0;
}while(lowlink[top] != idx[top]);
}
void solve(int nod)
{
S.push(nod);
isInStack[nod] = 1;
viz[nod] = 1;
idx[nod] = index;
lowlink[nod] = index;
index ++;
for(auto &v:graph[nod])
{
if(viz[v] == 0)
{
solve(v);
lowlink[nod] = min(lowlink[nod], lowlink[v]);
}
else{
if(isInStack[v] == 1)
lowlink[nod] = min(lowlink[nod], lowlink[v]);
}
}
if(lowlink[nod] == idx[nod])
{
addCC();
}
}
void tarjan()
{
// init();
for(int i = 1; i <= n; ++i)
if(viz[i] == 0)
solve(i);
}
void write()
{
g<<nrc<<"\n";
for(int i = 1; i <= nrc; ++i)
{
for(auto &v:CC[i])
g<<v<<" ";
g<<'\n';
}
}
int main()
{
read();
tarjan();
write();
return 0;
}
*/
/*
Ionut28
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int nmax = 100005;
int n, m, nrctc;
stack < int > S;
int viz[nmax];
vector < int > G[nmax], GT[nmax], CTC[nmax];
void read()
{
fin >> n >> m;
for(int i = 1; i <= m; ++i)
{
int x, y;
fin >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void DFS1(int nod)
{
viz[nod] = 1;
for(unsigned int i = 0; i < G[nod].size(); ++i)
{
int vecin = G[nod][i];
if(!viz[vecin])
DFS1(vecin);
}
S.push(nod);
}
void DFS2(int nod)
{
viz[nod] = 2;
CTC[nrctc].push_back(nod);
for(unsigned int i = 0; i < GT[nod].size(); ++i)
{
int vecin = GT[nod][i];
if(viz[vecin] == 1)
DFS2(vecin);
}
}
void solve()
{
for(int i = 1; i <= n; ++i)
if(!viz[i])
DFS1(i);
while(!S.empty())
{
int nod = S.top();
if(viz[nod] == 1)
{
nrctc++;
DFS2(nod);
}
S.pop();
}
}
void afisare()
{
fout << nrctc << "\n";
for(int i = 1; i <= nrctc; ++i)
{
for(unsigned int j = 0; j < CTC[i].size(); ++j)
fout << CTC[i][j] << " ";
fout << "\n";
}
}
int main()
{
read();
solve();
afisare();
return 0;
}*/
/*
AlbertUngureanu
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M, nR;
bool Viz[100005],VizT[100005];
vector<int>Ad[100005],AdT[100005],Ord,TareCon[100005];
void citire()
{
int x,y;
fin>>N>>M;
for(int i=1;i<=M;i++)
{
fin>>x>>y;
Ad[x].push_back(y);
AdT[y].push_back(x);
}
}
void sortareTopologica(int x)
{
Viz[x]=1;
for(unsigned i=0;i<Ad[x].size();i++)
if(!Viz[Ad[x][i]])
sortareTopologica(Ad[x][i]);
Ord.push_back(x);
}
void DFS(int x)
{
VizT[x]=1;
TareCon[nR].push_back(x);
for(unsigned i=0;i<AdT[x].size();i++)
if(!VizT[AdT[x][i]])
DFS(AdT[x][i]);
}
int main()
{
citire();
for(int i=1;i<=N;i++)
if(!Viz[i])
sortareTopologica(i);
for(int x=(int)Ord.size()-1;x>=0;x--)
if(!VizT[Ord[x]])
{
nR++;
DFS(Ord[x]);
}
fout<<nR<<'\n';
for(int i=1;i<=nR;i++)
{
for(unsigned j=0;j<TareCon[i].size();j++)
fout<<TareCon[i][j]<<" ";
fout<<'\n';
}
return 0;
}
*/