Pagini recente » Borderou de evaluare (job #271870) | Borderou de evaluare (job #1452017) | Cod sursa (job #3144603) | Borderou de evaluare (job #362212) | Cod sursa (job #511777)
Cod sursa(job #511777)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <string>
using namespace std;
class Vertex {
private:
int nod;
int pre;
public:
Vertex() { nod=-1; pre=-1;}
Vertex(int nodd, int pree) { nod=nodd; pre=pree; }
int get_nod() const { return nod; }
int get_pre() const { return pre; }
void set_pre(int pree) {pre=pree;}
bool operator==(const Vertex &other) const { return (this->get_nod()==other.get_nod()); }
bool operator!=(const Vertex &other) const { return (this->get_nod()!=other.get_nod()); }
};
vector<vector<int>> ll; vector<int> ln; Vertex* noduri; int c=0; stack<Vertex> S,P;
int n,m; vector<vector<int>> a; vector<int> l;
void add(int i, int j)
{
ll[i].push_back(j);
}
void initializare_lista(int n)
{
for (int i=0; i<=n-1; i++) ll.push_back(ln);
}
void initializare()
{
ifstream fis;
fis.open("ctc.in");
fis>>n; fis>>m;
if (!(n>=1 && n<=100000 && m>=1 && m<=200000)) return;
noduri=new Vertex[n];
for (int i=0; i<=n-1; i++) noduri[i]=Vertex(i,-1);
initializare_lista(n);
int i=1,a,b;
while (i<=m)
{
fis>>a;
fis>>b;
add(a-1,b-1);
++i;
}
}
bool exista(vector<vector<int>> a, int nod)
{
for (size_t i=0; i<a.size(); i++)
for (size_t j=0; j<a[i].size(); j++)
if (a[i][j]==nod) return true;
return false;
}
bool e_vecin(int lni, int col)
{
for (size_t j=0; j<ll[lni].size(); j++)
if (ll[lni][j]==col) return true;
return false;
}
void gabow(Vertex ver)
{
ver.set_pre(c);
noduri[ver.get_nod()].set_pre(c);
++c;
S.push(ver); P.push(ver);
for (int i=0; i<=n-1; i++)
if (e_vecin(ver.get_nod(),i))
{
if (noduri[i].get_pre()==-1) gabow(noduri[i]);
else
if (!exista(a,i))
{
Vertex vr=P.top();
while(vr.get_pre() > noduri[i].get_pre())
{
P.pop();
vr=P.top();
}
}
}
if (ver==P.top())
{
Vertex vr;
do
{
vr=S.top();
l.push_back(vr.get_nod());
S.pop();
}
while(vr!=ver);
a.push_back(l);
l.clear();
P.pop();
}
}
void dfs()
{
for (int i=0; i<=n-1; i++)
if (noduri[i].get_pre()==-1)
gabow(noduri[i]);
}
void afisare_scc()
{
ofstream fis;
fis.open("ctc.out");
fis<<a.size()<<endl;
for (size_t i=0; i<a.size(); i++)
{
for (size_t j=0; j<a[i].size(); j++)
fis<<a[i][j]+1<<" ";
fis<<endl;
}
}
int main()
{
initializare();
if (n>=1 && n<=100000 && m>=1 && m<=200000)
{
dfs();
afisare_scc();
}
return 0;
}